PROBLEM STATEMENT:
We are given an array which is a rotated (clockwise ) version of a sorted array. We need to find how many rotations are performed in the original sorted array to get the given array.
QUICK POINTS:
It can be seen that the number of rotation performed in the array will be equal to the index of the minimum element. See the example:
17 18 20 1 3 4 5 6 10 15
ALGORITHM:
1. Find the middle element.
2. If the middle element is greater than the next element, then the index of minimum element will be mid+1 (see the example, if we can find 20 as the middle element, then 1 is the minimum element).
3. If the middle index is strictly greater than the left index and the middle element is less than the previous element, then the index of minimum element will be middle index. ( See in the example, if 1 is middle element, 20 is greater than 1, so 1 is the minimum element.
4. If middle element is less than the right most element, search in the left part of the middle index.
5. If middle element is greater than left element, search in the right part of the middle index.
CODE:
#include <bits/stdc++.h>
using namespace std;
int minelement(int l,int r, int a[])
{ if(l>r)
return 0;
if(l==r)
return l;
if(r>=l)
{
int mid=l+(r-l)/2;
if(mid<r && a[mid]>a[mid+1])
return mid+1;
if(mid>l && a[mid]<a[mid-1])
return mid;
if(a[mid]<a[r])
return minelement(l,mid-1,a);
if(a[mid]>a[l])
return minelement(mid+1,r,a);
}
}
int main()
{
int n; //size of array
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int ans=minelement(0,n-1,a);
cout<<ans;
return 0;
}
INPUT:
10
17 18 20 1 3 4 5 6 10 15
OUTPUT:
3
0 Comments