Number of right cyclic shifts to give the biggest number

Question

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;
    }

Answer 1

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.

Answer 2

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;
   

Answer 3

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.