CareerCup

As question is how many rotation has been done in array.....
so if rotation is more then 'Array.length()' we can never find out how exactly rotation were there in array....

all we can find out is how many places array moved from initial position.

binary search, keep going to the half where first elem > last elem, until you find a[i]>a[i+1]. for example, 6 7 8 1 2 3 4 5=>6 7 8 1=>8 1. index of 1 is # times rotated.

Loop for length of array:{if(ary[i]<=ary[i+1]){
count++;
i++;
}else{
break;
}}

Let us assume that the array is initially sorted in ascending order.
And rotation be moving the elements in the clock-wise direction (one element shift is one rotation)

int rotation(int r[],int size)
{
	int low = 0;
	int high = size-1;
	int middle = (low+high)/2;
	while(middle>low)
	{
		if(r[middle]<r[high])
			high = middle;
		else
			low = middle;
		middle = (high+low)/2;
	}
	return middle+1;
}

1 2 3 4 5 - Original Sorted Array
5 1 2 3 4 - 1 Rotate
4 5 1 2 3 - 2 Rotate
3 4 5 1 2 - 3 rotate
2 3 4 5 1 - 4 rotate
1 2 3 4 5 - 5 rotate or no rotate

public class RotatingArrayExample {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
	
		Integer arr[] = {4,5,1,2,3};
		
		System.out.println("No. of rotate : " + findNumOfTimesRotated(arr)); 
	}

	static int findNumOfTimesRotated(Integer arr[])
	{
		int i=0;
		for (i = 0 ; i < arr.length-1 ; i++)
		{
			
			 if (arr[i] > arr[i+1])
			 	 break;
		}	
		if (i==arr.length-1)
			i=-1; // No rotation
		return i+1;
		
	}
}

public class RotatedArrayTime {

	public static void main(String[] args) {

		int arr[]=new int[]{5,6,7,8,9,10,11,12,13,14,15,16,17,18,1,2,3,4};
		int index=binarySearch(0,arr.length,arr);
		System.out.println(index);
	}
	
	private static int binarySearch(int start,int end,int[] arr)
	{
		int mid=start+(end-start)/2;
		int index=-1;
		if(arr[mid]<arr[mid-1] && arr[mid]< arr[mid+1])
		{
			index=mid;
		}
		else if(arr[start]<arr[mid])
		{
			index=binarySearch(mid+1,arr.length,arr);
		}
		else
		{
			index= binarySearch(0,mid-1,arr);
		}
		
		return index;
	}

}

[Assumption: Array has unique elements. I am working on a generic solution.]

The following is a hybrid of Binary Search and selection sort select logic. To summarize I can do this if I can find the index of the minimum element in the sorted array. For example

1 2 3 4 5 - Original Sorted Array
5 1 2 3 4 - 1 Rotate (Notice index of the minimum element is 1)
4 5 1 2 3 - 2 Rotate (Notice index of the minimum element is 2)
3 4 5 1 2 - 3 Rotate (Notice index of the minimum element is 3)
2 3 4 5 1 - 4 Rotate (Notice index of the minimum element is 4)
1 2 3 4 5 - 5 rotate or no rotate (Notice index of the minimum element is 0)

For number of rotations >= array length lets assume it was never rotated
When I say selection sort, I mean the way you find the min/max in the unsorted array and update its position. In our case the array is sorted but rotated. We can choose which direction my min is going to be by using binary search like logic and eliminating half of the entries each time.

Here is a code that can find this in O(log(n)) for you.

public static int findNumRotation(int[] a) {
        if (a.length <= 1) {
            return 0;
        }

        int beg = 0, end = a.length - 1, mid, temp, index;
        temp = a[0];
        index = 0;

        while (beg <= end) {

            mid = (beg + end) / 2;

            if (a[mid] < temp) {
                temp = a[mid];
                index = mid;
            }

            if (a[mid] <= a[end]) {
                end = mid - 1;
            } else {
                beg = mid + 1;
            }
        }

        return index;
    }

public static int findNumRotation(int[] a) {
if (a.length <= 1) {
return 0;
}

int beg = 0, end = a.length - 1, mid, temp, index;
temp = a[0];
index = 0;

while (beg <= end) {

mid = (beg + end) / 2;

if (a[mid] < temp) {
temp = a[mid];
index = mid;
}

if (a[mid] <= a[end]) {
end = mid - 1;
} else {
beg = mid + 1;
}
}

return index;
}

This above code is not working plz check

My turn to take a stab at it

/* To find the number of rotations in an array in less than O(n) time */

#include <stdio.h>

void findRotations(int arr[], int size);

int main(void)
{
	
	int arr1[]={7,8,9,10,1,2,3,4,5,6};	
	int size1=sizeof(arr1)/sizeof(arr1[0]);	//Size of arr1[]
	
	
	int arr2[]={4,5,6,7,8,9,10,1,1,1,2,3};
	int size2=sizeof(arr2)/sizeof(arr2[0]);	//Size of arr2[]
	
	
	findRotations(arr1, size1);	//Calling function, passing arr1[]
	
	findRotations(arr2, size2);	//Calling function, passing arr2[]
	
	
	return 0;
	
}


//Function that employs binary search to find the number of rotations
void findRotations(int arr[], int size)
{
	
	if(size==0 || size==1 || size==2)
		return;
	
	int l=0, r=size-1, mid=l+(r-l)/2;
	
	//Logic is to zero-in on the smallest element in the array using binary search
	while(l<=r)
	{
		
		if(arr[mid-1]>arr[mid] && arr[mid]<=arr[mid+1])	//Minimum found condition
		{
			printf("\nNo. of rotations are %d or %d\n", mid, size-mid);
			return;
		} 
		
		
		else if(arr[mid]-arr[l]<0)	//Passing this condition binary search would 
			r=mid-1;				//continue on the left sub-array
			
		
		else
			l=mid+1;
			
		
		mid=l+(r-l)/2;
	}
	
	return;
}

why can not this work ... my solution is just o(1)+o(1)

calculate a[mid] with left+right/2
if(mid+1)<a[mid] //left rotated
if(mid+1>a[mid]) //right rotated
else no rotation

In order to find the rotations in a sorted array we can adopt the solution.
T(n) = T(n/2) + c divide and conquer technique resulting in a O(lgn) solution.
The interesting part of this problem is that whether the array is sorted in
ascending order or descending order... I tried to solve this with ascending and
descending order then I think over the combined solution...

Any improvement and suggestions are highly appreciated.

int find_r(int a[], int start, int end) {

	while (start < end) {
		int mid = start + (end - start)/2;

		// ascending  if (a[mid] > a[end])
		// descending if (a[mid] < a[end])
		
		// both
		if (where_to_go(a, start, mid, end))	
			start = mid + 1;
		else
			end = mid;
	}

	return start;
}

Now the tricky part is decide where to go either on the left or on the right.
for this we've to analyse two arrays...

// A = <8,7,6,5,9,10> -- right rotated, rotations = 2.
// B = <6,7, 1,2,3,4> -- left rotated, rotations = 2.

if we correctly guess the whether it's ascending or descending sequence this would solve
the problem.

bool where_to_go(int a[], int start, int mid, int end) {
	
	if (a[mid] < a[start] && a[mid] < a[end]) {		// descending
		
		if (a[mid] < a[end])	// go to right.
			return true;
		else 
			return false;
			
	} else {		// ascending.
	
		if (a[mid] > a[end])	// go to right.
			return true;
		else 
			return false;
	}
}

a O(logn) solution

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

int arr[]={5,6,7,1,2,3,4};
int n=7;

int find()
{
int l=0, r=6, m, idx=0;
while(r-l>1)
{
m=(l+r)>>1;
if(arr[l]>arr[m])
r=m, idx=m;
else
l=m;
}
//cout<<idx<<endl;
if(arr[l]>arr[r]) idx=r;
int ret=min(idx, n-idx);
return ret;
}

int main()
{
int res=find();
cout<<res;
return 0;
}

int count_rotate(int a[],int l,int u)
{
while(a[l]>a[u-1])
l++;
return l;
}

We can use the concept of inversion and remove the merge operation from the code ...

My code is as follows

#include<iostream>
#include<cstdio>

void count_the_rotation(int *a,int p,int q,int r,int *i)
{
    if(a[q]>a[q+1])
    {
        *i=q;
    }
}
void array_rotation_count(int *a,int p,int r,int *i)
{
    if(p<r)
    {
        int q=(p+r)/2;
        array_rotation_count(a,p,q,i);
        array_rotation_count(a,q+1,r,i);
        count_the_rotation(a,p,q,r,i);
    }
}
int main()
{
    int a[]={3,4,5,6,1,2};
    int i=-1;
    array_rotation_count(a,0,5,&i);
    std::cout<<"The number of rotations the array has undergone is :"<<i+1;
}

youtube {dot} com/watch?v=4qjprDkJrjY
This should be the perfect solution and explanation to everyone's doubts over the question.

Can be easily done by using binary search

#include<iostream>
#include<stdio.h>
using namespace std;
 
int findRotation(int *arr,int length)   {
    int low=0;
    int high=length-1;
    
    while(low<=high) {
        int mid=(int)(low+high)/2;
        if(arr[mid]>arr[mid-1] && arr[mid]>arr[mid+1])
            return mid+1;
        else if(arr[mid]<arr[mid+1] && arr[mid]>arr[mid-1])  {
            high=mid-1;
        }
        else
            low=mid+1;
    }
    
    return -1;
}
 
 
int main()  {
    int arr[]={13,20,22,24,2,3,4};
    int NRotation=findRotation(arr,7);
    cout<<NRotation;
}

int findRotation(int* array, int low, int high){
	if(array[low] < array[high])    // It is a sorted array.
		return -1;
	int middle;
	while(low < high){
		middle = low + (high - low) >>1 ;
		if (array[middle - 1] > array[middle])   // found the index;
			return middle;
		if (array[low] < array [middle]) // left is sorted, check right.
			low = middle - 1;
		else if (array[middle] < array[high]) // right is sorted, check left.
			high = middle + 1;
	}
	return  -1;
}

In python:

def findRotations(s):
    m = len(s)/2
    l = 0
    h = len(s) - 1

    while l < h:
        if s[l] < s[h]:
            # already sorted
            return l
        m = (l + h)/2
        if s[m] < s[m-1] and s[m] < s[m+1]:
            # must be min
            return m
        elif s[m] >= s[l]:
            # must be in other half
            l = m+1
        elif s[m] <= s[h]:
            # must be in this half
            h = m-1

    return m + 1