Quickly Find Multiple Left Rotations of Array in C
Quickly Find Multiple Left Rotations of an Array in C: A Comprehensive Tutorial
Given an array of size n and multiple values k representing the number of left rotations, the task is to efficiently find the rotated array for each query. Instead of rotating the array for each query separately (which would be O(n × q)), we can preprocess the array to answer each query in O(n) time (for printing) with O(1) overhead.
This tutorial provides an in-depth exploration of quickly finding multiple left rotations: naive repeated rotation, doubled array preprocessing, and space-optimized modular indexing approaches, with practical implementation, common pitfalls, and best practices.
Conceptual Introduction & Fundamentals
What is the Problem?
Given an array and multiple queries k1, k2, k3, ..., kq, find the array after left rotating by each k positions.
Example:
text
Array: [1, 3, 5, 7, 9] Queries: k = 2, 3, 4 Left rotate by 2: [5, 7, 9, 1, 3] Left rotate by 3: [7, 9, 1, 3, 5] Left rotate by 4: [9, 1, 3, 5, 7]
Why This Problem Matters
- Multiple queries: Efficient handling of repeated rotation requests.
- Preprocessing: Trade-off between space and time.
- Algorithm design: Demonstrates the power of precomputation.
- Real-world applications: Circular buffers, data streaming, cyclic scheduling.
- Interview preparation: Common coding interview question.
Key Insight
After k left rotations, the element at position i in the rotated array is arr[(i + k) % n]. This simple observation enables O(1) rotation lookup.
Approaches Overview
| Approach | Preprocessing | Per Query | Space |
|---|---|---|---|
| Naive repeated rotation | None | O(n) | O(n) |
| Doubled array | O(n) | O(n) | O(n) |
| Modular indexing | None | O(n) | O(1) |
Syntax & Core Mechanics
Approach 1: Naive Repeated Rotation
For each query, rotate the array by k positions.
c
#include <stdio.h> #include <stdlib.h> #include <string.h> void reverse(int arr[], int start, int end) { while (start < end) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } void leftRotate(int arr[], int n, int k) { k %= n; if (k == 0) return; reverse(arr, 0, k - 1); reverse(arr, k, n - 1); reverse(arr, 0, n - 1); } void printArray(const int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main(void) { int original[] = {1, 3, 5, 7, 9}; int n = sizeof(original) / sizeof(original[0]); int queries[] = {2, 3, 4, 6, 14}; int q = sizeof(queries) / sizeof(queries[0]); for (int i = 0; i < q; i++) { int *arr = malloc(n * sizeof(int)); if (arr == NULL) return 1; memcpy(arr, original, n * sizeof(int)); leftRotate(arr, n, queries[i]); printArray(arr, n); free(arr); } return 0; } Expected output:
text
5 7 9 1 3 7 9 1 3 5 9 1 3 5 7 3 5 7 9 1 9 1 3 5 7
Time: O(n) per query, Space: O(n)
Approach 2: Doubled Array Preprocessing
Create a temporary array of size 2n containing two copies of the original array. For each query, print n elements starting from index k % n.
c
#include <stdio.h> #include <stdlib.h> #include <string.h> void preprocess(const int arr[], int n, int temp[]) { for (int i = 0; i < n; i++) { temp[i] = arr[i]; temp[i + n] = arr[i]; } } void leftRotate(const int temp[], int n, int k) { int start = k % n; for (int i = start; i < start + n; i++) { printf("%d ", temp[i]); } printf("\n"); } int main(void) { int arr[] = {1, 3, 5, 7, 9}; int n = sizeof(arr) / sizeof(arr[0]); int *temp = malloc(2 * n * sizeof(int)); if (temp == NULL) return 1; preprocess(arr, n, temp); int queries[] = {2, 3, 4, 6, 14}; int q = sizeof(queries) / sizeof(queries[0]); for (int i = 0; i < q; i++) { leftRotate(temp, n, queries[i]); } free(temp); return 0; } Expected output:
text
5 7 9 1 3 7 9 1 3 5 9 1 3 5 7 3 5 7 9 1 9 1 3 5 7
Preprocessing: O(n), Per query: O(n), Space: O(n)
Approach 3: Space-Optimized Modular Indexing
Without extra space, use modular arithmetic to access elements directly.
c
#include <stdio.h> void leftRotate(const int arr[], int n, int k) { k %= n; for (int i = k; i < k + n; i++) { printf("%d ", arr[i % n]); } printf("\n"); } int main(void) { int arr[] = {1, 3, 5, 7, 9}; int n = sizeof(arr) / sizeof(arr[0]); int queries[] = {2, 3, 4, 6, 14}; int q = sizeof(queries) / sizeof(queries[0]); for (int i = 0; i < q; i++) { leftRotate(arr, n, queries[i]); } return 0; } Expected output:
text
5 7 9 1 3 7 9 1 3 5 9 1 3 5 7 3 5 7 9 1 9 1 3 5 7
Preprocessing: None, Per query: O(n), Space: O(1)
Full Practical Code Example with Explanation
This program demonstrates all three approaches with verification, performance comparison, and edge cases.
Program: Multiple Left Rotations Demo
c
/** * multiple_left_rotations.c * Demonstrates approaches to quickly find multiple left rotations. * Compares naive, doubled array, and modular indexing 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 */ void reverse(int arr[], int start, int end); void leftRotateInPlace(int arr[], int n, int k); void printRotatedNaive(const int arr[], int n, int k); void preprocessDoubled(const int arr[], int n, int temp[]); void printRotatedDoubled(const int temp[], int n, int k); void printRotatedModular(const int arr[], int n, int k); int readInteger(const char *prompt, int *outValue); void printArray(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("=== Multiple Left Rotations Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate All Approaches\n"); printf("2. Custom Array with Multiple Queries\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, q; 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:\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; } } if (readInteger("Enter number of queries: ", &q) != 0) { fprintf(stderr, "Invalid q.\n"); break; } printf("\nOriginal: "); printArray(arr, n); /* Preprocess for doubled approach */ int *temp = malloc(2 * n * sizeof(int)); if (temp == NULL) { fprintf(stderr, "Memory allocation failed.\n"); break; } preprocessDoubled(arr, n, temp); printf("\nResults:\n"); for (int i = 0; i < q; i++) { int k; char prompt[50]; snprintf(prompt, sizeof(prompt), "Query %d k: ", i + 1); if (readInteger(prompt, &k) != 0) { fprintf(stderr, "Invalid k.\n"); i--; continue; } printf(" k=%-4d | Naive: ", k); printRotatedNaive(arr, n, k); printf(" | Doubled: "); printRotatedDoubled(temp, n, k); printf(" | Modular: "); printRotatedModular(arr, n, k); } free(temp); 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; } /* Reverses array portion */ void reverse(int arr[], int start, int end) { while (start < end) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } /* In-place left rotation using reversal algorithm */ void leftRotateInPlace(int arr[], int n, int k) { if (n <= 1) return; k %= n; if (k == 0) return; reverse(arr, 0, k - 1); reverse(arr, k, n - 1); reverse(arr, 0, n - 1); } /* Naive: rotate a copy and print */ void printRotatedNaive(const int arr[], int n, int k) { int *copy = malloc(n * sizeof(int)); if (copy == NULL) return; memcpy(copy, arr, n * sizeof(int)); leftRotateInPlace(copy, n, k); printArray(copy, n); free(copy); } /* Preprocess doubled array */ void preprocessDoubled(const int arr[], int n, int temp[]) { for (int i = 0; i < n; i++) { temp[i] = arr[i]; temp[i + n] = arr[i]; } } /* Print using doubled array */ void printRotatedDoubled(const int temp[], int n, int k) { int start = k % n; printf("["); for (int i = start; i < start + n; i++) { printf("%d", temp[i]); if (i < start + n - 1) printf(", "); } printf("]\n"); } /* Print using modular indexing */ void printRotatedModular(const int arr[], int n, int k) { k %= n; printf("["); for (int i = k; i < k + n; i++) { printf("%d", arr[i % n]); if (i < k + n - 1) printf(", "); } printf("]\n"); } /* 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 all three approaches */ void demonstrateApproaches(void) { printf("\n=== All Approaches ===\n"); int arr[] = {1, 3, 5, 7, 9}; int n = sizeof(arr) / sizeof(arr[0]); int queries[] = {2, 3, 4, 6, 14}; int q = sizeof(queries) / sizeof(queries[0]); printf("Original: "); printArray(arr, n); printf("\n"); int *temp = malloc(2 * n * sizeof(int)); if (temp == NULL) return; preprocessDoubled(arr, n, temp); for (int i = 0; i < q; i++) { int k = queries[i]; printf("k = %d\n", k); printf(" Naive: "); printRotatedNaive(arr, n, k); printf(" Doubled: "); printRotatedDoubled(temp, n, k); printf(" Modular: "); printRotatedModular(arr, n, k); printf("\n"); } free(temp); } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison (n = 100000, q = 10) ===\n"); int n = 100000; int q = 10; int *arr = malloc(n * sizeof(int)); int *temp = malloc(2 * n * sizeof(int)); if (arr == NULL || temp == NULL) { fprintf(stderr, "Memory allocation failed.\n"); free(arr); free(temp); return; } for (int i = 0; i < n; i++) arr[i] = i; preprocessDoubled(arr, n, temp); clock_t start, end; double timeTaken; /* Naive */ start = clock(); for (int i = 0; i < q; i++) { int *copy = malloc(n * sizeof(int)); memcpy(copy, arr, n * sizeof(int)); leftRotateInPlace(copy, n, i * 100); free(copy); } end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Naive (rotate copy): %.3f ms\n", timeTaken); /* Doubled */ start = clock(); for (int i = 0; i < q; i++) { int k = i * 100; int startIdx = k % n; volatile long sum = 0; for (int j = startIdx; j < startIdx + n; j++) { sum += temp[j]; } (void)sum; } end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Doubled array: %.3f ms\n", timeTaken); /* Modular */ start = clock(); for (int i = 0; i < q; i++) { int k = i * 100; volatile long sum = 0; for (int j = k; j < k + n; j++) { sum += arr[j % n]; } (void)sum; } end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Modular indexing: %.3f ms\n", timeTaken); free(arr); free(temp); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); int arr[] = {1, 3, 5, 7, 9}; int n = sizeof(arr) / sizeof(arr[0]); /* Case 1: k = 0 */ printf("Case 1: k = 0 (no rotation)\n"); printRotatedModular(arr, n, 0); /* Case 2: k = n */ printf("\nCase 2: k = n (full rotation, no change)\n"); printRotatedModular(arr, n, n); /* Case 3: k > n */ printf("\nCase 3: k = 14 > n = 5 (k %% n = 4)\n"); printRotatedModular(arr, n, 14); /* Case 4: Single element */ int arr2[] = {42}; printf("\nCase 4: Single element\n"); printRotatedModular(arr2, 1, 3); /* Case 5: k = n - 1 */ printf("\nCase 5: k = n - 1 = 4\n"); printRotatedModular(arr, n, 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
- Naive: Copies and rotates for each query; O(n) per query.
- Doubled: Preprocesses 2n array; O(n) per query for printing.
- Modular: No preprocessing; O(n) per query for printing with O(1) space.
Expected Output (sample run)
text
=== Multiple Left Rotations Demo === --- Menu --- 1. Demonstrate All Approaches 2. Custom Array with Multiple Queries 3. Performance Comparison 4. Edge Cases 5. Exit Enter choice: 1 === All Approaches === Original: [1, 3, 5, 7, 9] k = 2 Naive: [5, 7, 9, 1, 3] Doubled: [5, 7, 9, 1, 3] Modular: [5, 7, 9, 1, 3] k = 3 Naive: [7, 9, 1, 3, 5] Doubled: [7, 9, 1, 3, 5] Modular: [7, 9, 1, 3, 5] k = 4 Naive: [9, 1, 3, 5, 7] Doubled: [9, 1, 3, 5, 7] Modular: [9, 1, 3, 5, 7] k = 6 Naive: [3, 5, 7, 9, 1] Doubled: [3, 5, 7, 9, 1] Modular: [3, 5, 7, 9, 1] k = 14 Naive: [9, 1, 3, 5, 7] Doubled: [9, 1, 3, 5, 7] Modular: [9, 1, 3, 5, 7] --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: k = 0 (no rotation) [1, 3, 5, 7, 9] Case 2: k = n (full rotation, no change) [1, 3, 5, 7, 9] Case 3: k = 14 > n = 5 (k % n = 4) [9, 1, 3, 5, 7] Case 4: Single element [42] Case 5: k = n - 1 = 4 [9, 1, 3, 5, 7]
Common Pitfalls, Edge Cases & Memory Considerations
1. Not Handling k > n
Forgetting k %= n causes out-of-bounds access.
c
int start = k; /* BUG if k > n */ int start = k % n; /* Correct */
Solution: Always apply k %= n.
2. Negative k
Negative k causes implementation-defined modulo results.
c
k = -1; k %= n; /* Implementation-defined */
Solution: Normalize: k = ((k % n) + n) % n;
3. Empty Array
Accessing arr[0] on empty array causes issues.
c
if (n <= 0) return; /* Required */
4. Single Element
A single-element array remains unchanged for any k.
c
int arr[] = {42}; /* Rotated by any k: [42] */ 5. Memory Leaks with Naive Approach
Forgetting to free the copy array.
c
int *copy = malloc(n * sizeof(int)); /* ... */ /* Missing free(copy); */
Solution: Always free dynamically allocated memory.
6. Overflow in i + n
For doubled array, ensure index stays within 2n.
c
for (int i = start; i < start + n; i++) /* start + n <= 2n */
7. Modular Indexing Correctness
arr[i % n] works correctly for non-negative i.
Solution: Ensure loop variable starts at k (non-negative after modulo).
8. Printing Format
Consistent formatting for readability.
c
printf("["); /* ... */ printf("]\n"); 9. Multiple Queries with Same k
Cache results if same k repeats.
Solution: Use a hash map or sort queries for optimization.
10. Memory Considerations
- Naive: O(n) extra space per query.
- Doubled: O(n) extra space once.
- Modular: O(1) extra space.
- Modular approach is preferred for memory-constrained environments.
Summary & Best Practices
Quickly finding multiple left rotations of an array involves preprocessing or using modular arithmetic to answer each query efficiently. The modular indexing approach is the most space-efficient.
Key Takeaways
- After
kleft rotations, elementibecomesarr[(i + k) % n]. - Naive: O(n) per query, O(n) space.
- Doubled array: O(n) preprocessing, O(n) per query, O(n) space.
- Modular: No preprocessing, O(n) per query, O(1) space.
- Always apply
k %= nto handle largek.
Best Practices
- Use modular indexing for space efficiency.
- Use doubled array when multiple queries benefit from preprocessing.
- Apply
k %= nto normalize rotation count. - Handle edge cases: empty array, single element,
k = 0,k = n. - Free dynamically allocated memory.
- Use
size_tfor array sizes where appropriate. - Validate input (array size,
krange). - Consistent output formatting for readability.
- Test with
k > nand negative values. - Profile for very large arrays and many queries.
By mastering this problem, you’ll efficiently handle multiple rotation queries and understand the trade-offs between preprocessing and on-the-fly computation.
