Rotation Count in Rotated Sorted Array in C

Rotation Count in a Rotated Sorted Array in C: A Comprehensive Tutorial

Given a sorted array that has been right-rotated k times, the task is to find the value of k. Right rotation means the last element moves to the first position, and all other elements shift one position right. The rotation count equals the index of the minimum element in the rotated array. Understanding this problem is essential for mastering binary search variations and rotated array manipulation.

This tutorial provides an in-depth exploration of finding the rotation count in a rotated sorted array in C: naive linear approach, optimized binary search, practical implementation, common pitfalls, and best practices.

---

Conceptual Introduction & Fundamentals

What is a Right-Rotated Sorted Array?

A sorted array that has been right-rotated k times. Each right rotation moves the last element to the front.

Example:

text

Original sorted: [2, 3, 6, 12, 15, 18] After 1 rotation: [18, 2, 3, 6, 12, 15] After 2 rotations: [15, 18, 2, 3, 6, 12]

The rotation count k = 2.

Key Insight

In a right-rotated sorted array:

• The minimum element is the pivot point.
• The index of the minimum element equals the number of right rotations k.

Example:

text

Array: [15, 18, 2, 3, 6, 12] Minimum: 2 at index 2 Rotation count: k = 2

Why This Problem Matters

• Binary search variants: Classic rotated array problem.
• Search in rotated arrays: Foundation for searching in rotated sorted arrays.
• Algorithm design: Teaches divide-and-conquer optimization.
• Interview preparation: Common coding interview question.
• Data processing: Understanding circular shifts.

Approaches Overview

Approach	Time Complexity	Space Complexity
Naive (linear scan)	O(n)	O(1)
Binary search	O(log n)	O(1)

---

Syntax & Core Mechanics

Approach 1: Naive Linear Scan

Scan the array to find the minimum element; its index is the rotation count.

c

#include <stdio.h> int findRotationCount(const int arr[], int n) { if (n <= 0) return -1; int minIndex = 0; int minValue = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] < minValue) { minValue = arr[i]; minIndex = i; } } return minIndex; } int main(void) { int arr[] = {15, 18, 2, 3, 6, 12}; int n = sizeof(arr) / sizeof(arr[0]); int k = findRotationCount(arr, n); printf("Rotation count: %d\n", k); return 0; }

Expected output:

text

Rotation count: 2

Time: O(n), Space: O(1)

Approach 2: Binary Search (Optimized)

Use binary search to find the minimum element in O(log n) time.

Key logic:

• If arr[low] <= arr[high], the subarray is sorted; minimum is at low.
• If arr[mid] > arr[high], minimum is in the right half.
• Otherwise, minimum is in the left half (could be mid).

c

#include <stdio.h> int findRotationCount(const int arr[], int n) { if (n <= 0) return -1; int low = 0; int high = n - 1; while (low <= high) { /* If subarray is sorted, minimum is at low */ if (arr[low] <= arr[high]) { return low; } int mid = low + (high - low) / 2; /* Check if mid is the minimum */ int next = (mid + 1) % n; int prev = (mid - 1 + n) % n; if (arr[mid] <= arr[next] && arr[mid] <= arr[prev]) { return mid; } /* Minimum is in right half */ if (arr[mid] > arr[high]) { low = mid + 1; } /* Minimum is in left half */ else { high = mid - 1; } } return low; } int main(void) { int arr[] = {15, 18, 2, 3, 6, 12}; int n = sizeof(arr) / sizeof(arr[0]); int k = findRotationCount(arr, n); printf("Rotation count: %d\n", k); return 0; }

Expected output:

text

Rotation count: 2

Time: O(log n), Space: O(1)

Simplified Binary Search

A cleaner version without explicit neighbor checks:

c

#include <stdio.h> int findRotationCount(const int arr[], int n) { if (n <= 0) return -1; int low = 0; int high = n - 1; while (low < high) { /* If subarray is sorted, minimum is at low */ if (arr[low] <= arr[high]) { return low; } int mid = low + (high - low) / 2; /* Minimum is in right half */ if (arr[mid] > arr[high]) { low = mid + 1; } /* Minimum is in left half (could be mid) */ else { high = mid; } } return low; } int main(void) { int arr[] = {15, 18, 2, 3, 6, 12}; int n = sizeof(arr) / sizeof(arr[0]); printf("Rotation count: %d\n", findRotationCount(arr, n)); return 0; }

Expected output:

text

Rotation count: 2

---

Full Practical Code Example with Explanation

This program demonstrates both approaches with verification, performance comparison, and edge cases.

Program: Rotation Count Finder

c

/** * rotation_count.c * Finds the rotation count in a right-rotated sorted array. * Compares naive and binary search approaches. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define MAX_SIZE 100000 /* Function prototypes */ int findRotationNaive(const int arr[], int n); int findRotationBinary(const int arr[], int n); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); int isSorted(const int arr[], int n); void demonstrateApproaches(void); void performanceComparison(void); void demonstrateEdgeCases(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Rotation Count Finder ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate with Sample Arrays\n"); printf("2. Enter Custom Array\n"); printf("3. Performance Comparison\n"); printf("4. Edge Cases\n"); printf("5. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: demonstrateApproaches(); break; case 2: { int arr[MAX_SIZE]; int n; if (readInteger("Enter array size (1-100000): ", &n) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (n < 1 || n > MAX_SIZE) { printf("Size must be 1-%d.\n", MAX_SIZE); break; } printf("Enter %d elements (sorted then right-rotated):\n", n); for (int i = 0; i < n; i++) { char prompt[50]; snprintf(prompt, sizeof(prompt), " Element %d: ", i); if (readInteger(prompt, &arr[i]) != 0) { fprintf(stderr, "Invalid input.\n"); n = i; break; } } printf("\nArray: "); printArray(arr, n); int naive = findRotationNaive(arr, n); int binary = findRotationBinary(arr, n); printf("Rotation count (naive): %d\n", naive); printf("Rotation count (binary): %d\n", binary); printf("Verification: %s\n", (naive == binary) ? "PASS" : "FAIL"); break; } case 3: performanceComparison(); break; case 4: demonstrateEdgeCases(); break; case 5: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Naive approach: O(n) */ int findRotationNaive(const int arr[], int n) { if (n <= 0) return -1; int minIndex = 0; for (int i = 1; i < n; i++) { if (arr[i] < arr[minIndex]) { minIndex = i; } } return minIndex; } /* Binary search approach: O(log n) */ int findRotationBinary(const int arr[], int n) { if (n <= 0) return -1; if (n == 1) return 0; int low = 0; int high = n - 1; while (low <= high) { /* If subarray is sorted, minimum is at low */ if (arr[low] <= arr[high]) { return low; } int mid = low + (high - low) / 2; int next = (mid + 1) % n; int prev = (mid - 1 + n) % n; /* Check if mid is the minimum */ if (arr[mid] <= arr[next] && arr[mid] <= arr[prev]) { return mid; } /* Minimum is in right half */ if (arr[mid] > arr[high]) { low = mid + 1; } /* Minimum is in left half */ else { high = mid - 1; } } return low; } /* Checks if array is sorted in ascending order */ int isSorted(const int arr[], int n) { for (int i = 1; i < n; i++) { if (arr[i] < arr[i - 1]) return 0; } return 1; } /* Prints array */ void printArray(const int arr[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) printf(", "); } printf("]\n"); } /* Demonstrates both approaches on sample arrays */ void demonstrateApproaches(void) { printf("\n=== Sample Arrays ===\n"); int arr1[] = {15, 18, 2, 3, 6, 12}; int n1 = sizeof(arr1) / sizeof(arr1[0]); printf("\nArray 1: "); printArray(arr1, n1); printf("Naive: %d\n", findRotationNaive(arr1, n1)); printf("Binary: %d\n", findRotationBinary(arr1, n1)); int arr2[] = {7, 9, 11, 12, 5}; int n2 = sizeof(arr2) / sizeof(arr2[0]); printf("\nArray 2: "); printArray(arr2, n2); printf("Naive: %d\n", findRotationNaive(arr2, n2)); printf("Binary: %d\n", findRotationBinary(arr2, n2)); int arr3[] = {7, 9, 11, 12, 15}; int n3 = sizeof(arr3) / sizeof(arr3[0]); printf("\nArray 3 (already sorted): "); printArray(arr3, n3); printf("Naive: %d\n", findRotationNaive(arr3, n3)); printf("Binary: %d\n", findRotationBinary(arr3, n3)); int arr4[] = {3, 4, 5, 1, 2}; int n4 = sizeof(arr4) / sizeof(arr4[0]); printf("\nArray 4: "); printArray(arr4, n4); printf("Naive: %d\n", findRotationNaive(arr4, n4)); printf("Binary: %d\n", findRotationBinary(arr4, n4)); } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison (n = 100000) ===\n"); int size = 100000; int *arr = malloc(size * sizeof(int)); if (arr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } /* Create a rotated sorted array with 12345 rotations */ int k = 12345; for (int i = 0; i < size; i++) { arr[i] = (i + k) % size; } printf("Array size: %d, Actual rotation: %d\n\n", size, k); clock_t start, end; double timeTaken; /* Naive approach */ start = clock(); int naiveResult = findRotationNaive(arr, size); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Naive (O(n)): Result = %d, Time = %.3f ms\n", naiveResult, timeTaken); /* Binary approach */ start = clock(); int binaryResult = findRotationBinary(arr, size); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Binary (O(log n)): Result = %d, Time = %.3f ms\n", binaryResult, timeTaken); free(arr); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Case 1: Empty array */ int arr1[] = {}; printf("Case 1: Empty array (n = 0)\n"); printf(" Result: %d (error code)\n", findRotationBinary(arr1, 0)); /* Case 2: Single element */ int arr2[] = {42}; printf("\nCase 2: Single element\n"); printf(" Array: "); printArray(arr2, 1); printf(" Rotation: %d\n", findRotationBinary(arr2, 1)); /* Case 3: Two elements, rotated once */ int arr3[] = {2, 1}; printf("\nCase 3: Two elements, rotated once\n"); printf(" Array: "); printArray(arr3, 2); printf(" Rotation: %d\n", findRotationBinary(arr3, 2)); /* Case 4: Already sorted */ int arr4[] = {1, 2, 3, 4, 5}; printf("\nCase 4: Already sorted\n"); printf(" Array: "); printArray(arr4, 5); printf(" Rotation: %d\n", findRotationBinary(arr4, 5)); /* Case 5: Rotated by n-1 */ int arr5[] = {2, 3, 4, 5, 1}; printf("\nCase 5: Rotated by n-1 = 4\n"); printf(" Array: "); printArray(arr5, 5); printf(" Rotation: %d\n", findRotationBinary(arr5, 5)); /* Case 6: All same elements */ int arr6[] = {5, 5, 5, 5}; printf("\nCase 6: All same elements\n"); printf(" Array: "); printArray(arr6, 4); printf(" Rotation: %d\n", findRotationBinary(arr6, 4)); } /* Reads an integer safely */ int readInteger(const char *prompt, int *outValue) { char buffer[MAX_LINE_LEN]; char *endPtr; long val; printf("%s", prompt); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { return -1; } errno = 0; val = strtol(buffer, &endPtr, 10); if (endPtr == buffer || (*endPtr != '\n' && *endPtr != '\0')) { return -1; } if (errno == ERANGE || val < -2147483647 - 1 || val > 2147483647) { return -1; } *outValue = (int)val; return 0; }

Explanation of Approaches

1. Naive: Linear scan finds minimum; its index is the rotation count.
2. Binary: Uses sorted property to narrow search to O(log n).
3. Verification: Both approaches must produce identical results.
4. Edge cases: Empty, single element, duplicates, already sorted.

Expected Output (sample run)

text

=== Rotation Count Finder === --- Menu --- 1. Demonstrate with Sample Arrays 2. Enter Custom Array 3. Performance Comparison 4. Edge Cases 5. Exit Enter choice: 1 === Sample Arrays === Array 1: [15, 18, 2, 3, 6, 12] Naive: 2 Binary: 2 Array 2: [7, 9, 11, 12, 5] Naive: 4 Binary: 4 Array 3 (already sorted): [7, 9, 11, 12, 15] Naive: 0 Binary: 0 Array 4: [3, 4, 5, 1, 2] Naive: 3 Binary: 3 --- Menu --- ... Enter choice: 3 === Performance Comparison (n = 100000) === Array size: 100000, Actual rotation: 12345 Naive (O(n)): Result = 12345, Time = 0.412 ms Binary (O(log n)): Result = 12345, Time = 0.001 ms --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: Empty array (n = 0) Result: -1 (error code) Case 2: Single element Array: [42] Rotation: 0 Case 3: Two elements, rotated once Array: [2, 1] Rotation: 1 Case 4: Already sorted Array: [1, 2, 3, 4, 5] Rotation: 0 Case 5: Rotated by n-1 = 4 Array: [2, 3, 4, 5, 1] Rotation: 4 Case 6: All same elements Array: [5, 5, 5, 5] Rotation: 0

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Empty Array

Accessing arr[0] on an empty array is undefined behavior.

c

if (n <= 0) return -1; // Required

Solution: Check n <= 0 before processing.

2. Single Element

A single-element array is trivially sorted; rotation count is 0.

c

if (n == 1) return 0;

Solution: Handle n == 1 explicitly.

3. Already Sorted Array

If the array is already sorted, rotation count is 0.

c

if (arr[low] <= arr[high]) return low; // Returns 0 for sorted

Solution: The base case handles this correctly.

4. Duplicate Elements

Duplicates can break binary search assumptions.

c

int arr[] = {2, 2, 2, 0, 2}; // Ambiguous minimum

Solution: For duplicates, fall back to linear scan or handle edge cases.

5. Integer Overflow in Mid Calculation

(low + high) / 2 can overflow for large indices.

c

int mid = (low + high) / 2; // BUG: potential overflow

Solution: Use low + (high - low) / 2.

6. Off-by-One in Binary Search

Incorrect loop bounds skip elements.

c

while (low < high) { // Correct for finding minimum /* ... */ }

Solution: Use consistent bounds.

7. All Elements Same

All elements same means rotation count is ambiguous (return 0).

c

int arr[] = {5, 5, 5, 5}; /* Any rotation gives same array; k = 0 is correct */

Solution: Return 0 for sorted-or-equal arrays.

8. Not Handling k = n

If rotated n times, array is back to original; k = 0.

Solution: d %= n or handle in logic.

9. Left Rotation Confusion

This problem uses right rotation. Left rotation count equals n - (right rotation count).

c

/* Right rotation count = index of minimum */ /* Left rotation count = n - index of minimum */

Solution: Document rotation direction clearly.

10. Memory Considerations

• Both approaches use O(1) extra space.
• No dynamic allocation required.
• Array size should fit in int or size_t.
• Binary search is preferred for large arrays.

---

Summary & Best Practices

Finding the rotation count in a right-rotated sorted array is a classic problem with an elegant O(log n) binary search solution. The rotation count equals the index of the minimum element.

Key Takeaways

• Right rotation count = index of minimum element.
• Naive approach: O(n) linear scan.
• Binary search approach: O(log n).
• Handle empty arrays, single elements, and already-sorted arrays.
• Duplicates may complicate binary search.
• Use low + (high - low) / 2 to avoid overflow.

Best Practices

1. Use binary search for O(log n) performance.
2. Check for empty arrays (n <= 0).
3. Handle single-element arrays (n == 1).
4. Return 0 for already-sorted arrays.
5. Document rotation direction (left vs right).
6. Test with duplicates if the array may contain them.
7. Use size_t for array sizes where appropriate.
8. Avoid integer overflow in mid calculation.
9. Verify with naive approach during testing.
10. Profile performance for large arrays.

By mastering this problem, you’ll understand binary search variations and be prepared for related problems like searching in rotated sorted arrays.