CareerCup

The problem is not clear. Assuming the problem is something like this,

Given array: 1,2,3,4,5,6 is a sorted array
Now the array is rotated 2 times and it becomes like: 5,6,1,2,3,4

Now we have to find the number of rotations which in this case is 2

Here is the logic,

I) One possible linear solution is very straight forward,
Scan through the array from left to right checking for the following condition,
if(a[i] > a[i+1])
i+1 is the number of rotations

II) Now to get a O(logn), we can do a binary search like this,

int findRotations(int a[], int firstIndex, int secondIndex, int last){

int middle = (firstIndex + secondIndex)/2;

if(a[middle] > a[middle +1] && a[middle] > a[last])
return middle +1;
else if(firstIndex == secondIndex)
return 0;
else if(a[middle] < a[middle +1] && a[middle] < a[last])
return findRotations(a, firstIndex, middle, last);
else
return findRotations(a, middle, secondIndex, last);
}

question not clear... pls elaborate

Your solution will not provide a correct answer if I did 8 rotations. In 8 rotations you will be getting the same output: 5,6,1,2,3,4. But according to your solution it is 2. How you are going to fig out that?

@particularraj

The above solution was designed based on the assumption that number of rotations will be between 0 to N. If the number of rotations go beyond N... then it is a cycle and there is no way to determine that. However, one possible output that could be displayed is,

In above example, you could display instead of just 2... print ((2 + NX), where N is the number of elements in the array and X is a number from 0 to some max number. So in the above example output will be (2+6X).

I cannot think of anything else. If any one has a better solution, please reply.

@particularraj

The above solution was designed based on the assumption that number of rotations will be between 0 to N. If the number of rotations go beyond N... then it is a cycle and there is no way to determine that. However, one possible output that could be displayed is,

In above example, you could display instead of just 2... print ((2 + NX), where N is the number of elements in the array and X is a number from 0 to some max number. So in the above example output will be (2+6X).

I cannot think of anything else. If any one has a better solution, please reply.

hhhmmm...I got you Tejas. Basically we have NO idea if it is rotating above N times. If there is any possible solution to fig out this, then I want to know :)

if we are only given input and output strings, then there is simply no way you can ever figure out the number of rotation if greater than N (i.e. you can only give the answer < N).

thanks anil for clearing this up.

what is "last" here??

Sorry for late reply.
number of rotations are less than N

consider the above binary search based solutions for test case
1,1,1,1,1,1,8,1,1
or
1,1,8,1,1,1,1,1,1

if its assumed that the original array is sorted, then an easy way is to find the first element of the rotated array in the original array through binary search. O(logn). if it is found in position k, then rotations = length of array - k .

length can be found in O(1) as size(array) / size(int)

i think parneeths soln is correct

int find_rot(int a[],int n)
{
int i = 0;
if(n>1)
{
while(a[i] < a[i+1])
i++;
}
return (i+1);
}