Given a circularly sorted array of integers, find the number of times the array is rotated. Assume there are no duplicates in the array and the rotation is in anti-clockwise direction.

For example,

**Input: **arr = [8, 9, 10, 2, 5, 6]

**Output: **The array is rotated 3 times

**Input: **arr = [2, 5, 6, 8, 9, 10]

**Output: **The array is rotated 0 times

If we carefully analyze the problem, we will see that

**Number of rotations = Number of elements before minimum element of the array OR index of the minimum element.**

A simple solution would be to run a **linear search** on the array and find the index of the minimum element. The problem with this approach is that its worst case time complexity is O(n). This solution also do not take advantage of the fact that the input is circularly sorted.

We can easily solve this problem in O(log(n)) time by **modifying binary search algorithm**. We have already reduced the problem to finding out the first element of the sorted sequence. The first element (Pivot) has one special property (lets call it pivot property) – both next and previous element of the pivot element are greater than it. No other element in the array will have this property except the pivot element. Since the array is circularly sorted,

- If pivot is the last element, then the first element will be considered as its next element.
- If pivot is the first element, then the last element will be considered as its previous element.

We know that the mid element always divides the array into two sub-arrays and pivot element can lie only in one of these halves. It is worth noticing that at-least one of these sub-arrays will always be sorted. If mid happens to be the point of rotation (minimum element), then both left and right sub-arrays will be sorted but but in any case one half (sub-array) must be sorted and we will make use of this property to discard left half or the right half at each iteration of the binary search.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <iostream> using namespace std; // Function to find the number of times the array is rotated int findRotationCount(int A[], int n) { // search space is A[low..high] int low = 0, high = n - 1; // iterate till search space contains at-least one element while (low <= high) { // if the search space is already sorted, we have // found the minimum element (at index low) if (A[low] <= A[high]) return low; int mid = (low + high) / 2; // find next and previous element of the mid element // (in circular manner) int next = (mid + 1) % n; int prev = (mid - 1 + n) % n; // if mid element is less than both its next and previous // neighbour, then it is the minimum element of the array if (A[mid] <= A[next] && A[mid] <= prev) return mid; // if A[mid..high] is sorted and mid is not the minimum element, // then pivot element cannot be present in A[mid..high] and // we can discard A[mid..high] and search in the left half else if (A[mid] <= A[high]) high = mid - 1; // if A[low..mid] is sorted then pivot element cannot be present in // it and we can discard A[low..mid] and search in the right half else if (A[mid] >= A[low]) low = mid + 1; } // invalid input return -1; } // main function int main() { int A[] = { 8, 9, 10, 2, 5, 6 }; int n = sizeof(A) / sizeof(A[0]); int count = findRotationCount(A, n); cout << "The array is rotated " << count << " times"; return 0; } |

**Output: **

The array is rotated 3 times

**Time complexity** of above solution is O(log(n)).

**Auxiliary space** used by the program is O(1).

**References:**

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply