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