0
\$\begingroup\$

I'm stuck on Codechef problem COOKMACH, which asks for the minimum number of operations needed to transform integer A into integer B, where each operation can be either doubling the number or halving it (rounding down). 1 ≤ A ≤ 107 and 1 ≤ B ≤ 107, and B is an integer power of 2.

In eclipse, the code runs in time, but when it is run in Codechef, the time limit is exceeded.

Is there anything that can be improved in code below?

BufferedReader b=new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(b.readLine());// no. of test cases
while(T>0){
    StringTokenizer s=new StringTokenizer(b.readLine());
    int count=0;
    int A =Integer.parseInt(s.nextToken());
    int B=Integer.parseInt(s.nextToken());
    if(A%2!=0){
        if(A<B){
            while(A!=1){
                A=(A-1)/2;
                count=A;
            }
            while(A<B){
                A=A*2;
                count++;
            }
        }
        else{
            while(A!=B){
                A=(A-1)/2;
                count++;
            }
        }
    }
    else{
        if(A<B){
            while(A!=B){
                A=A*2;
                count++;
            }
        }
        else{
            while(A!=B){
                A=A/2;
                count++;
            }
        }
    }
    T--;
}
}
}
\$\endgroup\$
3
\$\begingroup\$
    if(A%2!=0){
        if(A<B){
            while(A!=1){
                A=(A-1)/2;
                count=A;
            }

This looks like a bug. Consider the case where A is 5 and B is 8 or more. A is odd, less than B, and not equal to 1, so it enters the while loop. First iteration A becomes 2. Second iteration we have \$(2-1)/2\$ which rounds down to become 0. Since 0 is not equal to 1, we loop again and have \$(0-1)/2\$ which rounds off to 0 (negative fractions rounds up, towards zero). But now we're back to 0. So it loops endlessly.

This is why I would recommend saying A > 1 rather than A != 1. Then you would have returned an answer (possibly wrong) quickly rather than gotten Time Limit Exceeded.

The worst part is that this is unnecessary. Integer arithmetic would have handled this correctly. You don't need to check for odd numbers. Normal integer arithmetic already rounds down.

The count=A; is also wrong. You'd want to increment count here as well, not set it to 1.

You also don't correctly handle values for A like 6. It's not odd, but it's not a power of two either. You should reduce it to 1, but you won't so long as it is less than B. Instead you'll endlessly double it until the program crashes.

\$\endgroup\$
3
\$\begingroup\$

Coding Style

  • Avoid using capital letters as variables. Use names in camelCase.
  • Give spaces in your expressions. How much space and where, like should a space be there between an if and (, is personally preference. But complete lack of it makes code hard to watch.
  • Use A *= 2 and A /= 2 instead of A = A*2 and A = A/2. This maybe a personal performance but I found it much simpler.

Solution

As the other answer says, the code contains an infinite loop so the time limit is exceed. And it quite a simple problem. If a < b, and both a and b are power of 2, the answer is log2(b) - log2(a). If a is not, bring it down to the nearest power of 2 by halving it.

If a > b, well, you think about it.

To compute log base 2 in integer, given that the number is a power of 2, instead using floating arithmetic, check it against all power of 2s. The numbers are under 10^7. You would find it under 17 checks, which takes a brink of an eye.

\$\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.