Last Updated: 2 Feb, 2023

Rotation

Easy

Asked in company

Solve now

Problem statement

You are given an array 'arr' having 'n' distinct integers sorted in ascending order. The array is right rotated 'r' times

Find the minimum value of 'r'.

Right rotating an array means shifting the element at 'ith' index to (‘i+1') mod 'n' index, for all 'i' from 0 to ‘n-1'.

Example:

Input: 'n' = 5 , ‘arr’ = [3, 4, 5, 1, 2]

Output: 3 

Explanation:
If we rotate the array [1 ,2, 3, 4, 5] right '3' times then we will get the 'arr'. Thus 'r' = 3.

Input format:

The first line contains an integer ‘n’, representing the size of the array ‘arr’.   
The second line contains ‘n’ integers, elements of ‘arr’.

Output Format:

Return an integer, value of ‘r’.

Note:

You don’t need to print anything, it has already been taken care of, just complete the given function.

Solve now

Approaches

01 Approach

Approach:

Since we are rotating a sorted array ‘r’ times to the right, the minimum element would also be rotated ‘r’ times to the right. Thus we can perform a linear search to find the index of the minimum element and that would be our answer.

Algorithm:

Initialise ‘index’ = 0
for ‘i’ from 0 to n-1:
- if ( arr[index] > arr[i])
  - index = i
return index

Solve now

02 Approach

Approach:

We can binary search on the array for the index of the minimum element. Let ‘low’ and ‘high’ represent the current range and ‘mid’ be the middle index of this range. If ‘arr[mid]’ > ‘arr[high]’ then the minimum value lies in the range ‘mid+1’ to ‘high’. Otherwise it lies in the range ‘low’ to ‘mid’.

Algorithm:

Initialise ‘low’ = 0, ‘high’ = ‘n-1’
Initialise ‘ans’ = 0
if(arr[low] <= arr[high])
- return 0
while(low<high)
- Initialise mid = (low+high)/2
- if(arr[mid] > arr[high])
  - low = mid+1
- else
  - high = mid
ans = low
return ans

Solve now