Given an array arr[] of size N having distinct numbers sorted in increasing order and the array has been right rotated (i.e, the last element will be cyclically shifted to the starting position of the array) k number of times, the task is to find the value of k.
Examples:
Input: arr[] = {15, 18, 2, 3, 6, 12}
Output: 2
Explanation: Initial array must be {2, 3, 6, 12, 15, 18}.
We get the given array after rotating the initial array twice.Input: arr[] = {7, 9, 11, 12, 5}
Output: 4Input: arr[] = {7, 9, 11, 12, 15};
Output: 0
Approach 1 (Using linear search): This problem can be solved using linear search.
If we take a closer look at examples, we can notice that the number of rotations is equal to the index of the minimum element. A simple linear solution is to find the minimum element and returns its index.
Illustration:
Consider the array arr[]={15, 18, 2, 3, 6, 12};
Initially minimum = 15, min_index = 0At i = 1: min = 15, min_index = 0
At i = 2: min = min(2, 15) = 2, min_index = 2
At i = 3: min = 2, min_index = 2
At i = 4: min = 2, min_index = 2
At i = 5: min = 2, min_index = 2The array is rotated twice to the right
Follow the steps mentioned below to implement the idea:
- Initialize two variables to store the minimum value and the index of that value.
- Traverse the array from start to the end:
- Find the minimum value and index where the minimum value is stored.
- Return the index of the minimum value.
Below is the code implementation of the above idea.
C++
// C++ program to find number of rotations // in a sorted and rotated array. #include <bits/stdc++.h> using namespace std; // Returns count of rotations for an array which // is first sorted in ascending order, then rotated int countRotations(int arr[], int n) { // We basically find index of minimum // element int min = arr[0], min_index = 0; for (int i = 0; i < n; i++) { if (min > arr[i]) { min = arr[i]; min_index = i; } } return min_index; } // Driver code int main() { int arr[] = { 15, 18, 2, 3, 6, 12 }; int n = sizeof(arr) / sizeof(arr[0]); cout << countRotations(arr, n); return 0; } // This code is contributed by Adutya Kumar(adityakumar129) |
C
// C program to find number of rotations // in a sorted and rotated array. #include <stdio.h> // Returns count of rotations for an array which // is first sorted in ascending order, then rotated int countRotations(int arr[], int n) { // We basically find index of minimum // element int min = arr[0], min_index = 0; for (int i = 0; i < n; i++) { if (min > arr[i]) { min = arr[i]; min_index = i; } } return min_index; } // Driver code int main() { int arr[] = { 15, 18, 2, 3, 6, 12 }; int n = sizeof(arr) / sizeof(arr[0]); printf("%d", countRotations(arr, n)); return 0; } // This code is contributed by Adutya Kumar(adityakumar129) |
Java
// Java program to find number of // rotations in a sorted and rotated // array. import java.io.*; import java.lang.*; import java.util.*; class LinearSearch { // Returns count of rotations for an // array which is first sorted in // ascending order, then rotated static int countRotations(int arr[], int n) { // We basically find index of minimum // element int min = arr[0], min_index = 0; for (int i = 0; i < n; i++) { if (min > arr[i]) { min = arr[i]; min_index = i; } } return min_index; } // Driver program to test above functions public static void main(String[] args) { int arr[] = { 15, 18, 2, 3, 6, 12 }; int n = arr.length; System.out.println(countRotations(arr, n)); } } // This code is contributed by Adutya Kumar(adityakumar129) |
Python3
# Python3 program to find number # of rotations in a sorted and # rotated array. # Returns count of rotations for # an array which is first sorted # in ascending order, then rotated def countRotations(arr, n): # We basically find index # of minimum element min = arr[0] min_index = 0 for i in range(0, n): if (min > arr[i]): min = arr[i] min_index = i return min_index; # Driver code arr = [15, 18, 2, 3, 6, 12] n = len(arr) print(countRotations(arr, n)) # This code is contributed by Smitha Dinesh Semwal |
C#
// c# program to find number of // rotations in a sorted and rotated // array. using System; class LinearSearch { // Returns count of rotations for an // array which is first sorted in // ascending order, then rotated static int countRotations(int []arr, int n) { // We basically find index of minimum // element int min = arr[0], min_index = 0; for (int i = 0; i < n; i++) { if (min > arr[i]) { min = arr[i]; min_index = i; } } return min_index; } // Driver program to test above functions public static void Main () { int []arr = {15, 18, 2, 3, 6, 12}; int n = arr.Length; Console.WriteLine(countRotations(arr, n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to find number // of rotations in a sorted // and rotated array. // Returns count of rotations // for an array which is first // sorted in ascending order, // then rotated function countRotations($arr, $n) { // We basically find index // of minimum element $min = $arr[0]; $min_index = 0; for ($i = 0; $i < $n; $i++) { if ($min > $arr[$i]) { $min = $arr[$i]; $min_index = $i; } } return $min_index; } // Driver code $arr = array(15, 18, 2, 3, 6, 12); $n = sizeof($arr); echo countRotations($arr, $n); // This code is contributed // by ajit ?> |
Javascript
<script> // Javascript program to find number of rotations // in a sorted and rotated array. // Returns count of rotations for an array which // is first sorted in ascending order, then rotated function countRotations(arr, n) { // We basically find index of minimum // element let min = arr[0], min_index = 0 for (let i = 0; i < n; i++) { if (min > arr[i]) { min = arr[i]; min_index = i; } } return min_index; } // Driver Code let arr = [15, 18, 2, 3, 6, 12]; let n = arr.length; document.write(countRotations(arr, n)); </script> |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Another Approach: (Using Linear Search):
Idea is that if the array is rotated so then their will be an element in the array which must greater than the next number to that element
for eg :
Input: arr[] = {3,4,5,1,2}
output: 3
Explanation to above example is that for 0 to 1 index array is sorted and also from 3 to 4 index array is sorted only at index 2, 3 array is unsorted because arr[2]>arr[3] so we can see that previous element (arr[2]) is greater than the the current element (arr[3]) . while traversing the array whenever we are able to find the current element is greater than the next element then we will return current element + 1
Follow the steps mentioned below to implement the idea:
- Traverse the array from 0 till N:
- Return index + 1, when the current element is greater than the next element and must check i+1 must be less then the size of array
- Else return 0.
Below is the code implementation of the above idea.
C++
#include <bits/stdc++.h> using namespace std; int countRotations(int arr[], int n) { // Traverse the array for (int i = 0; i < n; i++) { // Index where element is greater than the next element if (arr[i] > arr[i + 1] && i+1 <n) { return i + 1; } } } // Array is not rotated return 0; } // Driver code int main() { int arr[] = { 15, 18, 2, 3, 6, 12 }; int n = sizeof(arr) / sizeof(arr[0]); cout << countRotations(arr, n); return 0; } |
Java
/*package whatever //do not write package name here */import java.io.*; class GFG { static int countRotations(int arr[], int n) { // Check is array is rotated if (arr[0] > arr[n - 1]) { // Traverse the array for (int i = 0; i < n; i++) { // Index where element is greater // than the next element if (arr[i] > arr[i + 1]) return i + 1; } } // Array is not rotated return 0; } public static void main(String[] args) { int arr[] = { 15, 18, 2, 3, 6, 12 }; int n = arr.length; System.out.println(countRotations(arr, n)); } } // This code is contributed by dhanshriborse561 |
Python3
def countRotations(arr, n): # Check is array is rotated if (arr[0] > arr[n - 1]): # Traverse the array for i in range(0, n): # Index where element is greater # than the next element if (arr[i] > arr[i + 1]): return i + 1 # Array is not rotated return 0 # Driver code arr = [15, 18, 2, 3, 6, 12] n = len(arr) print(countRotations(arr, n)) # This code is contributed by karandeep1234 |
C#
// Include namespace system using System; public class GFG { public static int countRotations(int[] arr, int n) { // Check is array is rotated if (arr[0] > arr[n - 1]) { // Traverse the array for (int i = 0; i < n; i++) { // Index where element is greater // than the next element if (arr[i] > arr[i + 1]) { return i + 1; } } } // Array is not rotated return 0; } public static void Main(String[] args) { int[] arr = {15, 18, 2, 3, 6, 12}; var n = arr.Length; Console.WriteLine(GFG.countRotations(arr, n)); } } // This code is contributed by aadityaburujwale. |
Javascript
// JS code to implement the approach function countRotations(arr, n) { // Check is array is rotated if (arr[0] > arr[n - 1]) { // Traverse the array for (let i = 0; i < n; i++) { // Index where element is greater // than the next element if (arr[i] > arr[i + 1]) return i + 1; } } // Array is not rotated return 0; } // Driver code let arr = [15, 18, 2, 3, 6, 12]; let n = arr.length; console.log(countRotations(arr, n)); // This code is contributed by adityamaharshi21 |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Approach 2: (Efficient Using Binary Search)
A better approach would be to perform binary searching, in place of linear search to find the position of the smallest element in the array.
Follow the steps mentioned below to implement the idea:
- The minimum element is the only element whose previous is greater than it. If there is no previous element, then there is no rotation (the first element is minimum).
- Check this condition for the middle element by comparing it with the (mid-1)th and (mid+1)th elements.
- If the minimum element is not at the middle (neither mid nor mid + 1), then
- If the middle element is smaller than the last element, then the minimum element lies in the left half
- Else minimum element lies in the right half.
Illustration:
Let the array be arr[]={15, 18, 2, 3, 6, 12}
low = 0 , high = 5.
=> mid = 2
=> arr[mid]=2 , arr[mid-1] > arr[mid] , hence condition is matched
=> The required index = mid = 2So the element is found at index 2.
Below is the implementation of the above approach.
C++
// Binary Search based C++ program to find number // of rotations in a sorted and rotated array. #include <bits/stdc++.h> using namespace std; // Returns count of rotations for an array which // is first sorted in ascending order, then rotated int countRotations(int arr[], int low, int high) { // This condition is needed to handle the case // when the array is not rotated at all if (high < low) return 0; // If there is only one element left if (high == low) return low; // Find mid int mid = low + (high - low) / 2; /*(low + high)/2;*/ // Check if element (mid+1) is minimum element. // Consider the cases like {3, 4, 5, 1, 2} if (mid < high && arr[mid + 1] < arr[mid]) return (mid + 1); // Check if mid itself is minimum element if (mid > low && arr[mid] < arr[mid - 1]) return mid; // Decide whether we need to go to left half or // right half if (arr[high] > arr[mid]) return countRotations(arr, low, mid - 1); return countRotations(arr, mid + 1, high); } // Driver code int main() { int arr[] = { 15, 18, 2, 3, 6, 12 }; int N = sizeof(arr) / sizeof(arr[0]); cout << countRotations(arr, 0, N - 1); return 0; } |
Java
// Java program to find number of // rotations in a sorted and rotated // array. import java.io.*; import java.lang.*; import java.util.*; class BinarySearch { // Returns count of rotations for an array // which is first sorted in ascending order, // then rotated static int countRotations(int arr[], int low, int high) { // This condition is needed to handle // the case when array is not rotated // at all if (high < low) return 0; // If there is only one element left if (high == low) return low; // Find mid // /*(low + high)/2;*/ int mid = low + (high - low) / 2; // Check if element (mid+1) is minimum // element. Consider the cases like // {3, 4, 5, 1, 2} if (mid < high && arr[mid + 1] < arr[mid]) return (mid + 1); // Check if mid itself is minimum element if (mid > low && arr[mid] < arr[mid - 1]) return mid; // Decide whether we need to go to left // half or right half if (arr[high] > arr[mid]) return countRotations(arr, low, mid - 1); return countRotations(arr, mid + 1, high); } // Driver program to test above functions public static void main(String[] args) { int arr[] = { 15, 18, 2, 3, 6, 12 }; int N = arr.length; System.out.println(countRotations(arr, 0, N - 1)); } } // This code is contributed by Chhavi |
Python3
# Binary Search based Python3 # program to find number of # rotations in a sorted and # rotated array. # Returns count of rotations for # an array which is first sorted # in ascending order, then rotated def countRotations(arr, n): start = 0 end = n-1 # Finding the index of minimum of the array # index of min would be equal to number to rotation while start<=end: mid = start+(end-start)//2 # Calculating the previous(prev) # and next(nex) index of mid prev = (mid-1+n)%n nex = (mid+1)%n # Checking if mid is minimum if arr[mid]<arr[prev]\ and arr[mid]<=arr[nex]: return mid # if not selecting the unsorted part of array elif arr[mid]<arr[start]: end = mid-1 elif arr[mid]>arr[end]: start = mid+1 else: return 0 # Driver code if __name__ == '__main__': arr = [15, 18, 2, 3, 6, 12] N = len(arr) print(countRotations(arr, N)) # This code is contributed by Smitha Dinesh Semwal |
C#
// C# program to find number of // rotations in a sorted and rotated // array. using System; class BinarySearch { // Returns count of rotations for an array // which is first sorted in ascending order, // then rotated static int countRotations(int[] arr, int low, int high) { // This condition is needed to handle // the case when array is not rotated // at all if (high < low) return 0; // If there is only one element left if (high == low) return low; // Find mid // /*(low + high)/2;*/ int mid = low + (high - low) / 2; // Check if element (mid+1) is minimum // element. Consider the cases like // {3, 4, 5, 1, 2} if (mid < high && arr[mid + 1] < arr[mid]) return (mid + 1); // Check if mid itself is minimum element if (mid > low && arr[mid] < arr[mid - 1]) return mid; // Decide whether we need to go to left // half or right half if (arr[high] > arr[mid]) return countRotations(arr, low, mid - 1); return countRotations(arr, mid + 1, high); } // Driver program to test above functions public static void Main() { int[] arr = { 15, 18, 2, 3, 6, 12 }; int N = arr.Length; Console.WriteLine(countRotations(arr, 0, N - 1)); } } // This code is contributed by vt_m. |
PHP
<?php // Binary Search based PHP // program to find number // of rotations in a sorted // and rotated array. // Returns count of rotations // for an array which is // first sorted in ascending // order, then rotated function countRotations($arr, $low, $high) { // This condition is needed // to handle the case when // array is not rotated at all if ($high < $low) return 0; // If there is only // one element left if ($high == $low) return $low; // Find mid $mid = $low + ($high - $low) / 2; // Check if element (mid+1) // is minimum element. Consider // the cases like {3, 4, 5, 1, 2} if ($mid < $high && $arr[$mid + 1] < $arr[$mid]) return (int)($mid + 1); // Check if mid itself // is minimum element if ($mid > $low && $arr[$mid] < $arr[$mid - 1]) return (int)($mid); // Decide whether we need // to go to left half or // right half if ($arr[$high] > $arr[$mid]) return countRotations($arr, $low, $mid - 1); return countRotations($arr, $mid + 1, $high); } // Driver code $arr = array(15, 18, 2, 3, 6, 12); $N = sizeof($arr); echo countRotations($arr, 0, $N - 1); // This code is contributed bu ajit ?> |
Javascript
<script> // Binary Search based C++ program to find number // of rotations in a sorted and rotated array. // Returns count of rotations for an array which // is first sorted in ascending order, then rotated function countRotations(arr, low, high) { // This condition is needed to handle the case // when the array is not rotated at all if (high < low) return 0; // If there is only one element left if (high == low) return low; // Find mid let mid = Math.floor(low + (high - low)/2); /*(low + high)/2;*/ // Check if element (mid+1) is minimum element. // Consider the cases like {3, 4, 5, 1, 2} if (mid < high && arr[mid+1] < arr[mid]) return (mid+1); // Check if mid itself is minimum element if (mid > low && arr[mid] < arr[mid - 1]) return mid; // Decide whether we need to go to left half or // right half if (arr[high] > arr[mid]) return countRotations(arr, low, mid-1); return countRotations(arr, mid+1, high); } // Driver code let arr = [15, 18, 2, 3, 6, 12]; let N = arr.length; document.write(countRotations(arr, 0, N-1)); // This code is contributed by Surbhi Tyagi. </script> |
Output
2
Time Complexity: O(log N)
Auxiliary Space: O(log N) [this is the space of recursion stack]
Iterative Code (Binary Search):
C++
#include <bits/stdc++.h> using namespace std; // Returns count of rotations // for an array which is first sorted // in ascending order, then rotated // Observation: We have to return // index of the smallest element int countRotations(int arr[], int n) { int low = 0, high = n - 1; if (arr[low] <= arr[high]) return 0; /*returns 0 if array is already sorted*/ while (low <= high) { // if first element is mid or // last element is mid // then simply use modulo so it // never goes out of bound. int mid = low + (high - low) / 2; int prev = (mid - 1 + n) % n; int next = (mid + 1) % n; if (arr[mid] <= arr[prev] && arr[mid] <= arr[next]) return mid; else if (arr[mid] <= arr[high]) high = mid - 1; else if (arr[mid] >= arr[0]) low = mid + 1; } return 0; } // Driver code int main() { int arr[] = { 15, 18, 2, 3, 6, 12 }; int n = sizeof(arr) / sizeof(arr[0]); cout << countRotations(arr, n); return 0; } |
Java
/*package whatever //do not write package name here */import java.io.*; class GFG { // Returns count of rotations // for an array which is first sorted // in ascending order, then rotated // Observation: We have to return // index of the smallest element static int countRotations(int[] arr, int n) { int low = 0, high = n - 1; while (low <= high) { // if first element is mid or // last element is mid // then simply use modulo so it // never goes out of bound. int mid = low + (high - low) / 2; int prev = (mid - 1 + n) % n; int next = (mid + 1) % n; if (arr[mid] <= arr[prev] && arr[mid] <= arr[next]) return mid; else if (arr[mid] <= arr[high]) high = mid - 1; else if (arr[mid] >= arr[low]) low = mid + 1; } return 0; } // Driver Code public static void main(String args[]) { int[] arr = { 15, 18, 2, 3, 6, 12 }; int n = arr.length; System.out.println(countRotations(arr, n)); } } // This code is contributed by shinjanpatra |
Python3
# Returns count of rotations for an array which # is first sorted in ascending order, then rotated # Observation: We have to return index of the smallest element def countRotations(arr, n): low = 0 high = n - 1 while(low <= high): # if first element is mid or # last element is mid # then simply use modulo # so it never goes out of bound. mid = low + ((high - low) // 2) prev = (mid - 1 + n) % n next = (mid + 1) % n if(arr[mid] <= arr[prev] and arr[mid] <= arr[next]): return mid elif (arr[mid] <= arr[high]): high = mid - 1 elif (arr[mid] >= arr[low]): low = mid + 1 return 0 # Driver code arr = [15, 18, 2, 3, 6, 12] n = len(arr) print(countRotations(arr, n)) # This code is contributed by shinjanpatra. |
C#
// C# program for the above approach using System; class GFG { // Returns count of rotations // for an array which is first sorted // in ascending order, then rotated // Observation: We have to return // index of the smallest element static int countRotations(int[] arr, int n) { int low = 0, high = n - 1; while (low <= high) { // if first element is mid or // last element is mid // then simply use modulo so it // never goes out of bound. int mid = low + (high - low) / 2; int prev = (mid - 1 + n) % n; int next = (mid + 1) % n; if (arr[mid] <= arr[prev] && arr[mid] <= arr[next]) return mid; else if (arr[mid] <= arr[high]) high = mid - 1; else if (arr[mid] >= arr[low]) low = mid + 1; } return 0; } // Driver Code public static void Main() { int[] arr = { 15, 18, 2, 3, 6, 12 }; int n = arr.Length; Console.Write(countRotations(arr, n)); } } // This code is contributed by saurabh_jaiswal. |
Javascript
<script> // Returns count of rotations for an array which // is first sorted in ascending order, then rotated //Observation: We have to return index of the smallest element function countRotations(arr, n) { let low =0 , high = n-1; while(low<=high){ let mid = low + Math.floor((high-low)/2) ; let prev = (mid-1 + n) %n , next = (mid+1)%n;//if first element is mid or //last element is mid then simply use modulo so it never goes out of bound. if(arr[mid]<=arr[prev] && arr[mid]<=arr[next]) return mid; else if (arr[mid]<=arr[high]) high = mid-1 ; else if (arr[mid]>=arr[low]) low=mid+1; } return 0; } // Driver code let arr = [15, 18, 2, 3, 6, 12]; let n = arr.length; document.write(countRotations(arr, n)); // This code is contributed by shinjanpatra. </script> |
Output
2
Time Complexity: O(log N)
Auxiliary Space: O(1), since no extra space has been taken.
Using Pivot:
Find the pivot in the array and return the pivot + 1 to get the rotation count in Rotated Sorted array.
Follow the steps mentioned below to implement the idea:
- Find out pivot point using binary search. We will set low pointer as the first array index and high with the last array index.
∗ From the high and low we will calculate the mid value.
∗ If the value at mid-1 is greater than the one at mid, return that value as the pivot.
∗ Else if the value at the mid+1 is less than mid, return mid value as the pivot.
∗ Otherwise, if value at low position is greater than mid position, consider the left half. Otherwise, consider the right half. - After getting pivot we find the number of rotation count in Rotated Sorted array by adding 1 to the pivot.
Below is the code implementation of the above idea.
C++
#include <iostream> using namespace std; // find the pivot int findPivot(int arr[], int n) { int low = 0, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (mid < high && arr[mid] > arr[mid + 1]) return mid; if (mid > low && arr[mid - 1] > arr[mid]) return mid - 1; if (arr[low] > arr[mid]) high = mid - 1; else low = mid + 1; } return -1; } // Returns count of rotations // for an array which is first sorted // in ascending order, then rotated int countRotations(int arr[], int n){ int pivot = findPivot(arr, n); return pivot + 1; } // Driver Code int main() { int arr[] = {15, 18, 2, 3, 6, 12}; int n = sizeof(arr)/sizeof(arr[0]); cout << countRotations(arr, n); return 0; } |
Java
// Java code to implement the approach class GFG { // Returns count of rotations // for an array which is first sorted // in ascending order, then rotated static int countRotations(int[] arr, int n) { int pivot = findPivot(arr, n); return pivot + 1; } // find the pivot static int findPivot(int[] arr, int n) { int low = 0, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (mid < high && arr[mid] > arr[mid + 1]) return mid; if (mid > low && arr[mid - 1] > arr[mid]) return mid - 1; if (arr[low] > arr[mid]) high = mid - 1; else low = mid + 1; } return -1; } // Driver Code public static void main(String args[]) { int[] arr = { 15, 18, 2, 3, 6, 12 }; int n = arr.length; System.out.println(countRotations(arr, n)); } } |
Python3
# Python code to implement the approach # Returns count of rotations # for an array which is first sorted # in ascending order, then rotated def countRotations(arr, n): pivot = findPivot(arr, n) return pivot + 1 # find the pivot def findPivot(arr, n): low = 0 high = n - 1 while low <= high: mid = low + (high - low) // 2 if mid < high and arr[mid] > arr[mid + 1]: return mid if mid > low and arr[mid - 1] > arr[mid]: return mid - 1 if arr[low] > arr[mid]: high = mid - 1 else: low = mid + 1 return -1 # Driver Code if __name__ == "__main__": arr = [15, 18, 2, 3, 6, 12] n = len(arr) print(countRotations(arr, n)) |
C#
using System; class GFG { // Returns count of rotations for an array which is first sorted in ascending order, then rotated static int countRotations(int[] arr, int n){ int pivot = findPivot(arr, n); return pivot + 1; } // find the pivot static int findPivot(int[] arr, int n){ int low = 0, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (mid < high && arr[mid] > arr[mid + 1]) return mid; if (mid > low && arr[mid - 1] > arr[mid]) return mid - 1; if (arr[low] > arr[mid]) high = mid - 1; else low = mid + 1; } return -1; } // Driver Code public static void Main(string[] args){ int[] arr = {15, 18, 2, 3, 6, 12}; int n = arr.Length; Console.WriteLine(countRotations(arr,n)); } } |
Javascript
// Returns count of rotations // for an array which is first sorted // in ascending order, then rotated function countRotations(arr, n) { const pivot = findPivot(arr, n); return pivot + 1; } // find the pivot function findPivot(arr, n) { let low = 0; let high = n - 1; while (low <= high) { const mid = low + Math.floor((high - low) / 2); if (mid < high && arr[mid] > arr[mid + 1]) { return mid; } if (mid > low && arr[mid - 1] > arr[mid]) { return mid - 1; } if (arr[low] > arr[mid]) { high = mid - 1; } else { low = mid + 1; } } return -1; } // Driver Code const arr = [15, 18, 2, 3, 6, 12]; const n = arr.length; console.log(countRotations(arr, n)); |
Output
2
Time Complexity: O(log N), where N is the size of the array
Auxiliary Space: O(1
This article is contributed by Rakesh Kumar. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
