Rotation Count - C++ Solution

1. Introduction

This blog post addresses a common problem in array manipulation - determining the rotation count of a circularly sorted array. In a circularly sorted array, elements are sorted in an increasing order, but the array is rotated a number of times in an anti-clockwise direction.

Problem

Given a circularly sorted array of distinct integers, the task is to find the total number of times the array has been rotated. The rotation is assumed to be in an anti-clockwise direction. This problem is a variant of binary search where the pivot point of the rotation needs to be identified.

2. Solution Steps

1. Implement a modified binary search to find the index of the minimum element (pivot).

2. The index of the minimum element indicates the number of rotations.

3. The key insight is that the minimum element is the only element whose previous element is greater than itself.

4. If the array is not rotated, then the minimum element is the first element.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to find the rotation count
int countRotations(const vector<int>& nums) {
    int low = 0, high = nums.size() - 1;

    while (low <= high) {
        if (nums[low] <= nums[high]) { // Case when the subarray is already sorted
            return low; // The array is rotated 'low' times
        }

        int mid = low + (high - low) / 2;
        int next = (mid + 1) % nums.size();
        int prev = (mid - 1 + nums.size()) % nums.size();

        // Check if mid element is the minimum element
        if (nums[mid] <= nums[next] && nums[mid] <= nums[prev]) {
            return mid;
        }

        // Decide whether to go left or right
        if (nums[mid] <= nums[high]) {
            high = mid - 1;
        } else if (nums[mid] >= nums[low]) {
            low = mid + 1;
        }
    }

    return -1; // This condition won't be reached for valid inputs
}

int main() {
    vector<int> nums = {8, 9, 10, 2, 5, 6};
    cout << "Rotation Count: " << countRotations(nums) << endl;
    return 0;
}

Output:

Rotation Count: 3

Explanation:

The function countRotations calculates the number of times a circularly sorted array is rotated. It searches for the position of the minimum element using a modified binary search. The position of this element gives the rotation count. For instance, in the array [8, 9, 10, 2, 5, 6], the minimum element is 2 at the 4th position (index 3), indicating the array is rotated 3 times. In a sorted array like [2, 5, 6, 8, 9, 10], the rotation count is 0 since the minimum element is at the beginning.