Home » Data Structure » Array Data Structure

Find the rotation count in rotated sorted array

C++ implementation to find the rotation count in rotated sorted array using multiple approaches.
Submitted by Vikneshwar GK, on February 23, 2022

Consider an ascendingly sorted integer array, of size n, that has distinct elements. This array is rotated in the clockwise direction, k number of times. The task at hand is to find the value of k.

Example:

Input:
array[]= {5, 1, 2, 3, 4}
            
Output:
Rotation Count: 1

Input:
array[]= {50, 60, 70, 30, 40}

Output:
Rotation Count: 3

Solution 1: Using Linear Search

This is a simple approach that involves searching the array in a linear fashion. If a take a closer look into the problem statement, we can notice that the value of k is the index value of the least element in that array. Therefore, finding the least element will get us the k value.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

// Function to find the k rotation value
int findRotationCount(int array[], int length)
{
    int min = array[0], index_min;
    for (int i = 0; i < length; i++) {
        if (min > array[i]) {
            min = array[i];
            index_min = i;
        }
    }
    return index_min;
}

// Main function
int main()
{
    int array[100], N, element;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }
    cout << "Rotation Count: " << findRotationCount(array, N);

    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1:5
Enter element 2:8
Enter element 3:1
Enter element 4:3
Enter element 5:4
Rotation Count: 2

Time Complexity: O(n), where n is the length of the array.

Solution 2: Using Binary Search

This is an efficient approach that is based on the idea that the minimum element is the one whose previous element is greater than itself, i.e. array[i-1] > array[i]. If it has no previous element, then we can conclude that the array is not rotated. Find this element involves following steps:

• Find the middle element in the array
• Compare it with array[mid-1] and array[mid+1]
• If the array[mid] is lesser than the last element, then the minimum element lies on the left half
• If the array[mid] is greater than the last element, then the minimum element lies on the right half
• Repeat these steps until the least element is found
• Print the index

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

// Function to find the k rotation value
int findRotationCount(int array[], int low, int high)
{
    // if array is not rotated
    if (high < low)
        return 0;

    // array contains only one element
    if (high == low)
        return low;

    // Find mid
    int mid = low + (high - low) / 2;

    // Check minimum for mid+1 and mid-1
    if (mid < high && array[mid + 1] < array[mid])
        return (mid + 1);

    if (mid > low && array[mid] < array[mid - 1])
        return mid;

    // Compare and call either left half or right half
    if (array[high] > array[mid])
        return findRotationCount(array, low, mid - 1);

    return findRotationCount(array, mid + 1, high);
}

// Main function
int main()
{
    int array[100], N, element;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }
    cout << "Rotation Count: " << findRotationCount(array, 0, N - 1);

    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1:7
Enter element 2:8
Enter element 3:9
Enter element 4:10
Enter element 5:2
Rotation Count: 4

Time Complexity: O(log(n)), where n is the length of the array.

Solution 3: Iterative Binary Search

This is same as above except this is implemented in an iterative approach rather than recursive.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

// Function to find the k rotation value
int findRotationCount(int array[], int length)
{
    int low = 0, high = length - 1;
    while (low <= high) {
        // find middle, previous and next element
        int mid = low + (high - low) / 2;
        int prev = (mid - 1 + length) % length;
        int next = (mid + 1) % length;

        // compare mid element with next and previous
        if (array[mid] <= array[prev] && array[mid] <= array[next])
            return mid;
        else if (array[mid] <= array[high])
            high = mid - 1;
        else if (array[mid] >= array[low])
            low = mid + 1;
    }
    return 0;
}

// Main function
int main()
{
    int array[100], N, element;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }
    cout << "Rotation Count: " << findRotationCount(array, N);

    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1:8
Enter element 2:9
Enter element 3:0
Enter element 4:1
Enter element 5:2
Rotation Count: 2

Time Complexity: O(log(n)), where n is the length of the array.