4
\$\begingroup\$

The question is to find a number with absolute minimum difference from a number of the form be. I came up with the below code which takes 4 seconds to solve each test case on an average however it has to be solved within 2 seconds.

Sample Input:

11
25

Sample Output:

2
0

Explanation:

11 is the nearest to 32. Thus 11 - 9 = 2

25 is 52 thus there is no difference.

My code:

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int T = in.nextInt();    //Number of testcases

    for(int i = 0; i < T; i++){

            int number = in.nextInt();

            int sqrtNumber = (int)Math.sqrt(number);                
            int powerNumber; 

            int minDiff = Integer.MAX_VALUE;
            for (int b = 2; b <= sqrtNumber; b++) {
                for (int e = 1; (powerNumber = (int) Math.pow(b, e)) <= number; e++) {
                    if (number - powerNumber < minDiff)
                        minDiff = number - powerNumber;
                }
            }
            System.out.println(minDiff);


    }
}
\$\endgroup\$
  • \$\begingroup\$ e should never be 1. (I think?) Don't think that would likely be enough to shave 2 seconds off though. \$\endgroup\$ – Dair Aug 13 '16 at 19:14
4
\$\begingroup\$

A big performance improvement can be made when you realize you don't need to loop over all the possible exponent e. The code calculates, for each possible e, the value of be, and calculating that power takes time.

The goal here is to find b and e such that be is the closest to an integer n. If we rewrite this, it also means finding b and e where \$e\log{b}\$ is closest to \$\log{n}\$. So for a given input number n, and a given base b, we know that the closest value we're looking for will have an exponent of \$e = \left\lfloor\frac{\log{n}}{\log{b}}\right\rfloor\$.

JS1 rightfully pointed out that calculating this formula can lead to rounding errors. Since we're dealing with whole numbers, we can add 0.5 before calculating the logarithm to account for that (I tested this for all numbers from 5 to 1000000). As such, for the inner loop, you can just have:

int sqrtNumber = (int) Math.sqrt(number);
double logN = Math.log(number + 0.5); // to account for rounding issues

int minDiff = Integer.MAX_VALUE;
for (int b = 2; b <= sqrtNumber; b++) {
    int e = (int) (logN / Math.log(b));
    int powerNumber = (int) Math.pow(b, e);
    if (number - powerNumber < minDiff) {
        minDiff = number - powerNumber;
    }
}

This code only makes a single power calculation, in order to know the actual difference between the power and the target number.

Here's a result of a JMH benchmark, comparing the initial code in the question and this revised code. The input number tested is 15000, 150000 and 1500000. This is very far to take 4 seconds for each case, but the revised code is 5 times faster (Windows 10, JDK 1.8.0_102 64 bits, i5 CPU @ 2.90 GHz).

Benchmark           (number)  Mode  Cnt  Score    Error  Units
StreamTest.initial     15000  avgt   30  0,023 ±  0,001  ms/op
StreamTest.initial    150000  avgt   30  0,068 ±  0,002  ms/op
StreamTest.initial   1500000  avgt   30  0,202 ±  0,002  ms/op
StreamTest.revised     15000  avgt   30  0,005 ±  0,001  ms/op
StreamTest.revised    150000  avgt   30  0,014 ±  0,001  ms/op
StreamTest.revised   1500000  avgt   30  0,041 ±  0,001  ms/op

Code of benchmark for completeness:

@Warmup(iterations = 10, time = 700, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 10, time = 700, timeUnit = TimeUnit.MILLISECONDS)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Fork(3)
public class StreamTest {

    @State(Scope.Benchmark)
    public static class NumberContainer {

        @Param({ "15000", "150000", "1500000" })
        private int number;

    }

    static int initialCode(int number) {
        int sqrtNumber = (int)Math.sqrt(number);                
        int powerNumber; 
        int minDiff = Integer.MAX_VALUE;
        for (int b = 2; b <= sqrtNumber; b++) {
            for (int e = 1; (powerNumber = (int) Math.pow(b, e)) <= number; e++) {
                if (number - powerNumber < minDiff)
                    minDiff = number - powerNumber;
            }
        }
        return minDiff;
    }

    static int revisedCode(int number) {
        int sqrtNumber = (int) Math.sqrt(number);
        double logN = Math.log(number + 0.5);
        int minDiff = Integer.MAX_VALUE;
        for (int b = 2; b <= sqrtNumber; b++) {
            int e = (int) (logN / Math.log(b));
            int powerNumber = (int) Math.pow(b, e);
            if (number - powerNumber < minDiff) {
                minDiff = number - powerNumber;
            }
        }
        return minDiff;
    }

    @Benchmark
    public int initial(NumberContainer c) {
        return initialCode(c.number);
    }

    @Benchmark
    public int revised(NumberContainer c) {
        return revisedCode(c.number);
    }

}
\$\endgroup\$
  • 1
    \$\begingroup\$ Your use of floating point causes roundoff errors. Try feeding 243 to your function. It will print 18 instead of 0 (32-bit X86). \$\endgroup\$ – JS1 Aug 15 '16 at 8:27
  • \$\begingroup\$ @JS1 Thanks! You're right and I corrected this. And +1 for your answer! \$\endgroup\$ – Tunaki Aug 15 '16 at 9:48
4
\$\begingroup\$

Can be much faster

The original code runs in approximately \$O(\sqrt n \log n)\$ time, and @Tunaki's version improves on that to run in roughly \$O(\sqrt n)\$ time.

However, you can actually do even better and achieve \$O(\log n)\$ time. Instead of iterating on trial numbers up to \$\sqrt n\$, you can instead iterate on exponents up to \$\log n\$. For each exponent \$e\$, you find the maximum \$b^e\$ less than or equal to \$n\$. This can be done in constant time by finding \$b\$ using the formula \$b = n^{1/e}\$, rounding \$b\$ down to the nearest int.

Floating point errors

Care must be taken when using floating point numbers. When computing b using the formula above, it is possible to round down too far by accident. For example, given n = 125 and e = 3, the formula should compute b = 5, but due to rounding errors, it might compute b = 4 instead.

Sample code

Here is some sample code to demonstrate the algorithm:

// Computes base ^ exp for integer exponents.  This function
// is much quicker than Math.pow().
static int intPow(int base, int exp)
{
    int ret    = 1;
    int factor = base;

    while (exp != 0) {
        if ((exp & 1) != 0)
            ret *= factor;
        factor *= factor;
        exp >>>= 1;
    }
    return ret;
}

// Given a number >= 4, find the highest integer b^e, where
// b^e <= number and e != 1, and then return (number - b^e).
static int findNumber(int number)
{
    int best = 1;

    // For each exponent 2..31, find the max base^exp <= number,
    // and return the best one.
    for (int exp = 2; exp < 32; exp++) {
        int base = (int) Math.pow(number, 1.0/exp);
        if (base <= 1)
            break;

        int n = intPow(base, exp);
        if (n > best)
            best = n;

        // Also test base+1 in case of rounding error.
        n = intPow(base+1, exp);
        if (n <= number && n > best)
            best = n;
    }
    return number - best;
}

Speed and accuracy

I didn't run a JMH benchmark, but I ran a quick test to see how long it would take to compute each answer from 5 to 500000. My test program ran in 4 seconds compared to @Tunaki's version which ran in 32 seconds.

For my program, I checked that the answer matched the original code for numbers 5..100000. I didn't check any higher due to lack of time. Theoretically, the code may need to corrected to handle the case of b being rounded up by one too many, but I did not ever encounter this so I omitted that case from my code.

@Tunaki's version did not match the original code's answer in all cases. For example, the input 243 returned 18 instead of 0. It could be modified to do handle the rounding error the same way as in my program. Also, I found that if you replace Math.pow() with intPow() in @Tunaki's version, it speeds i up by over 2x.

Revision

Borrowing from @Tunaki's new revision, instead of trying two different bases, we can be assured of having the correct base without a rounding error if we add 0.5 to the number before taking the root. Since we are only looking for integer roots, this should work without ever rounding up or down incorrectly. So the revised code would be:

// Given a number >= 4, find the highest integer b^e, where
// b^e <= number and e != 1, and then return (number - b^e).
static int findNumber(int number)
{
    int best = 1;

    // For each exponent 2..31, find the max base^exp <= number,
    // and return the best one.
    for (int exp = 2; exp < 32; exp++) {
        int base = (int) Math.pow(number + 0.5, 1.0/exp);
        if (base <= 1)
            break;

        int n = intPow(base, exp);
        if (n > best)
            best = n;
    }
    return number - best;
}
\$\endgroup\$
1
\$\begingroup\$

try with resources

    Scanner in = new Scanner(System.in);

My IDE complains because this is never closed.

    try (Scanner in = new Scanner(System.in)) {

Now it will close the Scanner automatically when it leaves the try block.

Not such a big deal with a Scanner. May matter more with other resources that follow the same pattern.

Indent odd

    for(int i = 0; i < T; i++){

            int number = in.nextInt();

This is an eight column indent, but everywhere else you only have a four column indent per level. Why not make this match?

    for (int i = 0; i < T; i++) {
        int number = in.nextInt();

Note that since you never use i or T except here, you could also say

    for (int T = in.nextInt(); T > 0; T--) {
        int number = in.nextInt();

Then you don't have to maintain an extra variable. Of course, you may find the other version more readable.

Don't repeat common operations

                    if (number - powerNumber < minDiff)
                        minDiff = number - powerNumber;

Note that number is constant for the entire for loop and minDiff only changes a small portion of the time. So calculate that after you finish.

    int closestValue = 1;

Note that \$1^e = 1\$ is the smallest possible power.

And then use it

                if (closestValue < powerNumber)
                    closestValue = powerNumber;

And finally change

            System.out.println(minDiff);

to

        System.out.println(number - closestValue);

This will produce the same result, but it moves a subtraction that you do on every iteration of the loop out of the loop. So you only do it once.

Don't use Math.pow when you could just multiply

You say

                for (int e = 1; (powerNumber = (int) Math.pow(b, e)) <= number; e++) {

Why not just say

            for (int powerNumber = b; powerNumber <= number; powerNumber *= b) {

This replaces an expensive power operation with a cheaper multiplication.

Go the other direction

            for (int b = 2; b <= sqrtNumber; b++) {

You start with the smallest possible base (2) and increase up to the square root. As a result, you have to update either minDiff or closestValue on every iteration of the inner loop.

        for (int b = (int)Math.sqrt(number); b >= 2; b--) {

Now you start with the largest possible base. So you update at most twice for any value of b.

A side benefit of this is that we can get rid of sqrtNumber as unnecessary. It was only needed previously since we used it in the loop comparison.

        for (int b = (int)Math.sqrt(number); b >= 2 && closestValue != number; b--) {

This short circuits if we find an exact match. Obviously we won't find a better match, so we can stop looking.

This should be benchmarked, since we don't know if it will stop early often enough to make up for the extra comparison.

Summary

public static void main(String[] args) {
    try (Scanner in = new Scanner(System.in)) {
        for (int T = in.nextInt(); T > 0; T--) {
            int number = in.nextInt();

            int closestValue = 1;
            for (int b = (int)Math.sqrt(number); b >= 2 && closestValue != number; b--) {
                for (int powerNumber = b; powerNumber <= number; powerNumber *= b) {
                    if (closestValue < powerNumber) {
                        closestValue = powerNumber;
                    }
                }
            }

            System.out.println(number - closestValue);
        }
    }
}

I would expect this to be faster than your original code, although @Tunaki's version is probably still faster than this for larger inputs.

\$\endgroup\$
0
\$\begingroup\$

Depending on how big the maximum test case can be, and how many test cases you are to get, it might be quicker to fill out a table of the answers for all possible cases. Then the test cases can be answered by just indexing into the table.

One way to fill out the table would be to first set the entries to 0 for all powers, and then to fill in the rest according to how far thay are from the nearest power.

Unfortunately I don't know java but in case it is of interest here is a C program that on my machine fills in (and prints) the table for the first million numbers in 70 milliseconds, while the fist 100 million numbers takes 7 seconds.

#include    <stdlib.h>
#include    <stdio.h>

int main( int argc, char** argv)
{   --argc; ++argv;
int64_t N = argc ? atoi( (--argc, *argv++)) : 1000000;
int64_t*    err = calloc( N, sizeof *err);
    // err 0,1 both 0
    // set the rest to something non-zero
int64_t i = N;
    while( --i >= 2)
    {   err[i] = -1;
    }
    // set all errors to zero for powers
    for( int64_t b=2; b*b<N; ++b)
    {   if ( !err[ b])
        {   continue;
        }
        for( int64_t p=b*b; p<N; p*=b)
        {   err[p] = 0;
        }
    }
    // set all others to distance from closest power
    // start at the end, find the first power
int64_t lo, hi;
    hi = N; while( err[--hi]);  // empty loop
    // set all above hi to distance from hi
    for( int64_t l=hi+1; l<N; ++l)      
    {   err[l] = l-hi;
    }
    while( hi>1)
    {   // find the next power below hi
        lo = hi; while( err[--lo]); // empty loop
        // fill in between lo and hi
        for( i=1; 2*i<=hi-lo; ++i)
        {   err[ lo+i] = err[ hi-i] = i;
        }
        hi = lo;
    }
    // output
    for( i=0; i<N/10; ++i)
    {   printf( "%6ld\t", 10*i);
        for( int64_t j=0; j<10; ++j)
        {   printf( "%.4ld ", err[10*i+j]);
        }
        printf( "\n");
    }
    free( err);
    return EXIT_SUCCESS;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.