3
\$\begingroup\$

I am preparing to coding interview and I met this task today:

You are given 30-bit unsigned integer N. A right cyclic shift of N by K bits is the result of performing a right cyclic shift of N by one bit K times. Leading zeros may appear.

For example:

  • the right cyclic shift of 9736 by one bit is 4868,
  • the right cyclic shift of 9736 by two bits is 2434,
  • the right cyclic shift of 9736 by eleven bits is 809500676

The number 809500676 is the largest value that can be obtained by performing a right cyclic shift of 9736.

The aim is to find integer K such that right cyclic shift of N by K bits gives the largest possible value. In example above method should return 11. 0<=N<=1073741823. Worst-case time complexity is O(log(N)).

My try should be correct value but does not meet (in my opinion, but I am not sure) time complexity.

    public int solution(int N) {
        long m = N;
        long max = N;
        int res = 0;
        for(int i =1;i<30;i++) {
            m=(N>>>i) & 0x3fffffff | (N<<(30-i)& 0x3fffffff);
            if(m>max) {
                max=m;
                res=i;
            }
        }
        return res;
    }
\$\endgroup\$
2
  • \$\begingroup\$ Can you use assembly? \$\endgroup\$ May 24, 2015 at 19:23
  • \$\begingroup\$ Java is preferred. If you meant that... \$\endgroup\$
    – marciano
    May 24, 2015 at 19:27

3 Answers 3

2
\$\begingroup\$

Just a tiny note on complexity. The complexity theory ignores constant factors and makes no sense for cases when the input can't grow without limits.

Worst-case time complexity is O(log(N)).

This can't be. Either you work with 30 bit numbers and make 30 iterations and there's a complexity of O(1) as the time is fixed. Or you allow an arbitrary number of bits and then you need an algorithm dealing with it. The running time for a straightforward implementation will be something like the number of bits squared, i.e., complexity O(log(N)**2). I guess, it can be optimized to the desired complexity, but that's a different task.

\$\endgroup\$
2
\$\begingroup\$

Two quick things:

  1. You don't have to use long anywhere, since everything fits in int.
  2. (x & MASK) | (y & MASK) can be simplified to (x | y) & MASK:

        m = (N >>> i | N << (30-i)) & 0x3fffffff;
    
\$\endgroup\$
2
\$\begingroup\$

Your solution seems fine. I would suggest some coding style improvements though:

  • To avoid errors, avoid magic numbers, put them in constants, for example:
    • MAX_N = 0x3fffffff
    • MAX_SHIFT = 30
  • The variable m doesn't need to be initialized before the loop. In fact, it doesn't need to be declared before the loop. Move it inside.
  • res is not a great name to store the number of shifts to get the highest number. shiftCount would be better.
  • solution is not a great name for the method to get the shift count for the highest number. getShiftCountToHighestNum would be better.

With the above suggestions applied, the code becomes:

private static final int MAX_N = 0x3fffffff;
private static final int MAX_SHIFT = Integer.toBinaryString(MAX_N).length();

public int getShiftCountToHighestNum(int N) {
    long max = N;
    int shiftCount = 0;
    for (int i = 1; i < MAX_SHIFT; i++) {
        long m = (N >>> i) & MAX_N | (N << (MAX_SHIFT - i) & MAX_N);
        if (m > max) {
            max = m;
            shiftCount = i;
        }
    }
    return shiftCount;
}

As for the time complexity, I believe this is indeed \$O(\log N)\$. The number of calculation steps is proportional to the number of bits in \$N\$, which grows much slower than \$N\$ itself.

\$\endgroup\$
3
  • \$\begingroup\$ You're replaced a magic number by a magic constant; what about MAX_N = (1 << MAX_SHIFT) - 1? \$\endgroup\$
    – maaartinus
    May 25, 2015 at 0:53
  • \$\begingroup\$ Good call, fixed it. Not by calculating MAX_N which is the given, but by setting MAX_SHIFT to Integer.toBinaryString(MAX_N).length(). Hope that's better. Thanks! \$\endgroup\$
    – janos
    May 25, 2015 at 5:40
  • \$\begingroup\$ Sure. It could be done more efficiently (which doesn't matter for a constent) using something like 32 - Integer.numberOfLeadingZeros, but this is always a bit error-prone (the opposite direction works for me perfectly). And there's also Guava's IntMath.log2. \$\endgroup\$
    – maaartinus
    May 25, 2015 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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