Find Number of Rotations
Mahabharata — The Wheel Count — How Many Times Was the Formation Rotated?
कति वारं सेना भ्रमिता? — न्यूनतमस्य स्थानं तत् उत्तरम्। येन स्थाने न्यूनतमः — तत् भ्रमणानाम् संख्या॥
*How many times was the army rotated? — The position of the minimum is the answer. Where the minimum stands — that is the rotation count.*
The Story
Given a sorted array that was rotated k times (right rotation), find k.
For `arr = [15,18,2,3,6,12]`, k=2 (rotated 2 times). Minimum is 2 at index 2. So k=2.
This is identical to bs-8 — find the minimum element's INDEX (not value).
**Why does the minimum's index equal the rotation count?** A right rotation by 1 moves the last element to the front. After k right rotations, the minimum that was at index 0 is now at index k.
Alternatively: after k right rotations, the sorted sequence starts at index k and wraps around.
```java int findKRotation(int[] arr) { int left=0, right=arr.length-1; while (left < right) { int mid = left+(right-left)/2; if (arr[mid] > arr[right]) left = mid+1; else right = mid; } return left; // Index of minimum = number of rotations } ```
Trace `[15,18,2,3,6,12]`: - l=0,r=5,mid=2,arr[2]=2 <= arr[5]=12 → right=2 - l=0,r=2,mid=1,arr[1]=18 > arr[2]=2 → left=2 - l==r=2 → return 2 ✓ (answer: 2 rotations)
"bs-8 returns nums[left] (the VALUE of minimum). bs-9 returns left (the INDEX of minimum). Same code, different return statement," Krishna summarized.
The Dip Finder
Find the index where arr[i] < arr[i-1]. That's the rotation point. O(n).
int findKRotationBruteForce(int[] arr) {
for (int i = 1; i < arr.length; i++)
if (arr[i] < arr[i-1]) return i;
return 0; // Not rotated
}The Minimum-Index Wisdom
int findKRotation(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] > arr[right]) left = mid + 1; // Disorder on right
else right = mid; // Min at mid or left
}
return left; // INDEX of minimum = rotation count
}Step-by-Step Walkthrough
[1,2,3,4,5] — no rotation l=0,r=4,mid=2,arr[2]=3<=arr[4]=5 → r=2 l=0,r=2,mid=1,arr[1]=2<=arr[2]=3 → r=1 l=0,r=1,mid=0,arr[0]=1<=arr[1]=2 → r=0 l==r=0 → return 0 (0 rotations) ✅
Deep Insight
**bs-8 vs bs-9: one character difference in the return statement.** - bs-8: `return nums[left];` (minimum VALUE) - bs-9: `return left;` (minimum INDEX = rotation count)
**If the array is not rotated:** The minimum is at index 0 → returns 0. Correct (0 rotations).
**Modular arithmetic connection:** An array of n elements rotated k times: element originally at index i is now at index (i + k) % n. The minimum (originally at index 0) is now at index k.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Scan for the dip |
| Optimal | O(log n) | O(1) | bs-8 returning index instead of value |
Pattern Recognition
✅ Rotation count = index of minimum element ✅ Same algorithm as bs-8 (find minimum in rotated array) ✅ Return INDEX (left) not VALUE (nums[left]) ✅ 0 rotations → returns 0 **LeetCode Trigger Phrases:** → "number of rotations in rotated sorted array" → "find rotation pivot" → Index of minimum in rotated array
Bhagavad Gita 11.32
कालोऽस्मि लोकक्षयकृत्प्रवृद्धो लोकान्समाहर्तुमिह प्रवृत्तः।
I am mighty Time, the source of destruction that has come forth to annihilate the worlds.
Connection: Time rotates the cosmic wheel — and the number of rotations is measured by finding where the cycle restarted. The minimum element in the rotated array marks the exact origin point of the current cycle. Like counting how many full revolutions the cosmic wheel has completed since its last reset, the algorithm measures rotation by pinpointing the moment of minimum — the origin of the current ordered sequence.