Rotation

Easy
0/40
profile
Contributed by
191 upvotes
Asked in company
EPAM Systems

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.


Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
4
2 3 4 1


Sample Output 1:
3


Explanation of sample output 1:
If we right rotate the array {1, 2, 3, 4} by '3' times then we will get {2, 3, 4, 1}. Thus 'r' = 3.


Sample Input 2:
3
1 2 3


Sample Output 2:
0


Explanation of sample output 2:
If we right rotate the array {1, 2, 3} by '0' time then we will get {1, 2, 3}. Thus 'r' = 0.


Expected time complexity:
Can you solve this in O(logn) time complexity?


Constraints:
1 <= ‘n’ <= 10^5    
1 <= ‘arr[i]’ <= 10^9
Time Limit: 1 sec
Hint

What does the position of the minimum element tell us?

Approaches (2)
Linear Search

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
Time Complexity

O(N), where ‘N’ is the number of elements in the array ‘arr’.
 

We are iterating through all the elements of ‘arr’ once, time complexity is

O(N).

Space Complexity

O(1)
 

We are not utilising any extra space.

Code Solution
(100% EXP penalty)
Rotation
Full screen
Console