Tag C programming

Rotate an Array – Clockwise or Right in C: A Comprehensive Tutorial

Array rotation is the process of rearranging the elements in an array by shifting each element to a new position. Right rotation (clockwise) shifts elements towards the right, with elements wrapping around from the end to the beginning. Understanding array rotation is essential for solving problems involving circular buffers, data shifting, and algorithmic puzzles.

This tutorial provides an in-depth exploration of right array rotation in C: multiple approaches, their time and space complexities, practical applications, common pitfalls, and best practices.

---

Conceptual Introduction & Fundamentals

What is Right Rotation?

Right rotation (clockwise rotation) by d positions moves each element d positions to the right. Elements that go past the last index wrap around to the beginning.

Example:

text

Original: [1, 2, 3, 4, 5, 6], d = 2 Rotated: [5, 6, 1, 2, 3, 4]

Why Array Rotation Matters

• Circular buffers: Implement queues and ring buffers.
• Data shifting: Move data windows in signal processing.
• Algorithm foundation: Rotated sorted arrays (binary search variations).
• Cryptography: Caesar cipher and similar ciphers.
• Image processing: Rotate pixel arrays.

Approaches Overview

Approach	Time Complexity	Space Complexity
Rotate one by one	O(n × d)	O(1)
Temporary array	O(n)	O(n)
Juggling algorithm	O(n)	O(1)
Reversal algorithm	O(n)	O(1)

Handling d > n

When d > n, we can reduce it using d % n because rotating by n positions returns the array to its original state.

text

d = 4, n = 3 → d % n = 1 (equivalent rotation)

---

Syntax & Core Mechanics

Approach 1: Rotate One by One

Rotate the array by one position d times.

c

#include <stdio.h> void rotateArrOneByOne(int arr[], int n, int d) { d %= n; /* Handle d > n */ for (int i = 0; i < d; i++) { int last = arr[n - 1]; /* Save last element */ /* Shift all elements right by one */ for (int j = n - 1; j > 0; j--) { arr[j] = arr[j - 1]; } arr[0] = last; /* Place last element at front */ } } int main(void) { int arr[] = {1, 2, 3, 4, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); int d = 2; rotateArrOneByOne(arr, n, d); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Expected output:

text

5 6 1 2 3 4

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

Approach 2: Temporary Array

Copy the last d elements to the front and the first n - d elements to the back.

c

#include <stdio.h> #include <stdlib.h> void rotateArrTemp(int arr[], int n, int d) { d %= n; if (d == 0 || n <= 1) return; int *temp = malloc(n * sizeof(int)); if (temp == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } /* Copy last d elements to front */ for (int i = 0; i < d; i++) { temp[i] = arr[n - d + i]; } /* Copy first n-d elements to back */ for (int i = 0; i < n - d; i++) { temp[d + i] = arr[i]; } /* Copy back to original */ for (int i = 0; i < n; i++) { arr[i] = temp[i]; } free(temp); } int main(void) { int arr[] = {1, 2, 3, 4, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); int d = 2; rotateArrTemp(arr, n, d); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Expected output:

text

5 6 1 2 3 4

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

Approach 3: Juggling Algorithm

Uses GCD to determine cycles; rotates elements within each cycle.

c

#include <stdio.h> int gcd(int a, int b) { while (b) { int temp = b; b = a % b; a = temp; } return a; } void rotateArrJuggling(int arr[], int n, int d) { d %= n; if (d == 0 || n <= 1) return; int cycles = gcd(n, d); for (int i = 0; i < cycles; i++) { int currIdx = i; int currEle = arr[currIdx]; do { int nextIdx = (currIdx + d) % n; int nextEle = arr[nextIdx]; arr[nextIdx] = currEle; currEle = nextEle; currIdx = nextIdx; } while (currIdx != i); } } int main(void) { int arr[] = {1, 2, 3, 4, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); int d = 2; rotateArrJuggling(arr, n, d); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Expected output:

text

5 6 1 2 3 4

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

Approach 4: Reversal Algorithm

Reverse the entire array, then reverse the first d elements, then reverse the remaining n - d elements.

c

#include <stdio.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 rotateArrReversal(int arr[], int n, int d) { d %= n; if (d == 0 || n <= 1) return; reverse(arr, 0, n - 1); /* Reverse entire array */ reverse(arr, 0, d - 1); /* Reverse first d elements */ reverse(arr, d, n - 1); /* Reverse remaining n-d elements */ } int main(void) { int arr[] = {1, 2, 3, 4, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); int d = 2; rotateArrReversal(arr, n, d); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Expected output:

text

5 6 1 2 3 4

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

---

Full Practical Code Example with Explanation

This program demonstrates all four rotation approaches with verification and performance comparison.

Program: Array Rotation Comparison

c

/** * array_rotation.c * Demonstrates multiple approaches to right rotate an array. * Includes verification, timing, and edge case handling. */ #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 rotateOneByOne(int arr[], int n, int d); void rotateTempArray(int arr[], int n, int d); void rotateJuggling(int arr[], int n, int d); void rotateReversal(int arr[], int n, int d); void reverse(int arr[], int start, int end); int gcd(int a, int b); void printArray(const int arr[], int n); int readInteger(const char *prompt, int *outValue); int arraysEqual(const int a[], const int b[], int n); void copyArray(const int src[], int dst[], int n); void demonstrateApproaches(void); void performanceComparison(void); void demonstrateEdgeCases(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Array Rotation (Right/Clockwise) Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate All Approaches\n"); printf("2. Custom Rotation\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, d, method; 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 rotation count d: ", &d) != 0) { fprintf(stderr, "Invalid d.\n"); break; } printf("\nOriginal: "); printArray(arr, n); printf("\nMethod:\n"); printf("1. One by One\n"); printf("2. Temporary Array\n"); printf("3. Juggling\n"); printf("4. Reversal\n"); printf("Enter method: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) break; method = atoi(buffer); switch (method) { case 1: rotateOneByOne(arr, n, d); break; case 2: rotateTempArray(arr, n, d); break; case 3: rotateJuggling(arr, n, d); break; case 4: rotateReversal(arr, n, d); break; default: printf("Invalid method.\n"); continue; } printf("Rotated by %d: ", d); printArray(arr, n); 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; } /* Approach 1: Rotate one by one */ void rotateOneByOne(int arr[], int n, int d) { if (n <= 1) return; d %= n; if (d == 0) return; for (int i = 0; i < d; i++) { int last = arr[n - 1]; for (int j = n - 1; j > 0; j--) { arr[j] = arr[j - 1]; } arr[0] = last; } } /* Approach 2: Temporary array */ void rotateTempArray(int arr[], int n, int d) { if (n <= 1) return; d %= n; if (d == 0) return; int *temp = malloc(n * sizeof(int)); if (temp == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } for (int i = 0; i < d; i++) { temp[i] = arr[n - d + i]; } for (int i = 0; i < n - d; i++) { temp[d + i] = arr[i]; } for (int i = 0; i < n; i++) { arr[i] = temp[i]; } free(temp); } /* Approach 3: Juggling algorithm */ int gcd(int a, int b) { while (b) { int temp = b; b = a % b; a = temp; } return a; } void rotateJuggling(int arr[], int n, int d) { if (n <= 1) return; d %= n; if (d == 0) return; int cycles = gcd(n, d); for (int i = 0; i < cycles; i++) { int currIdx = i; int currEle = arr[currIdx]; do { int nextIdx = (currIdx + d) % n; int nextEle = arr[nextIdx]; arr[nextIdx] = currEle; currEle = nextEle; currIdx = nextIdx; } while (currIdx != i); } } /* Approach 4: Reversal algorithm */ 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 rotateReversal(int arr[], int n, int d) { if (n <= 1) return; d %= n; if (d == 0) return; reverse(arr, 0, n - 1); reverse(arr, 0, d - 1); reverse(arr, d, n - 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"); } /* Compares arrays */ int arraysEqual(const int a[], const int b[], int n) { for (int i = 0; i < n; i++) { if (a[i] != b[i]) return 0; } return 1; } /* Copies array */ void copyArray(const int src[], int dst[], int n) { memcpy(dst, src, n * sizeof(int)); } /* Demonstrates all approaches */ void demonstrateApproaches(void) { printf("\n=== All Rotation Approaches ===\n"); int original[] = {1, 2, 3, 4, 5, 6}; int n = sizeof(original) / sizeof(original[0]); int d = 2; int expected[] = {5, 6, 1, 2, 3, 4}; int arr[MAX_SIZE]; printf("Original: [1, 2, 3, 4, 5, 6], d = 2\n"); printf("Expected: [5, 6, 1, 2, 3, 4]\n\n"); copyArray(original, arr, n); rotateOneByOne(arr, n, d); printf("One by One: "); printArray(arr, n); printf(" Verify: %s\n", arraysEqual(arr, expected, n) ? "PASS" : "FAIL"); copyArray(original, arr, n); rotateTempArray(arr, n, d); printf("Temp Array: "); printArray(arr, n); printf(" Verify: %s\n", arraysEqual(arr, expected, n) ? "PASS" : "FAIL"); copyArray(original, arr, n); rotateJuggling(arr, n, d); printf("Juggling: "); printArray(arr, n); printf(" Verify: %s\n", arraysEqual(arr, expected, n) ? "PASS" : "FAIL"); copyArray(original, arr, n); rotateReversal(arr, n, d); printf("Reversal: "); printArray(arr, n); printf(" Verify: %s\n", arraysEqual(arr, expected, n) ? "PASS" : "FAIL"); } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison (n = 100000, d = 12345) ===\n"); int size = 100000; int d = 12345; int *original = malloc(size * sizeof(int)); int *arr = malloc(size * sizeof(int)); if (original == NULL || arr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); free(original); free(arr); return; } for (int i = 0; i < size; i++) { original[i] = i; } clock_t start, end; double timeTaken; copyArray(original, arr, size); start = clock(); rotateTempArray(arr, size, d); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Temp Array: %.3f ms\n", timeTaken); copyArray(original, arr, size); start = clock(); rotateJuggling(arr, size, d); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Juggling: %.3f ms\n", timeTaken); copyArray(original, arr, size); start = clock(); rotateReversal(arr, size, d); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Reversal: %.3f ms\n", timeTaken); free(original); free(arr); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Case 1: d = 0 */ int arr1[] = {1, 2, 3, 4, 5}; int n1 = 5; printf("Case 1: d = 0\n"); printf(" Before: "); printArray(arr1, n1); rotateReversal(arr1, n1, 0); printf(" After: "); printArray(arr1, n1); /* Case 2: d > n */ int arr2[] = {1, 2, 3}; int n2 = 3; int d2 = 4; printf("\nCase 2: d = 4 > n = 3 (d %% n = 1)\n"); printf(" Before: "); printArray(arr2, n2); rotateReversal(arr2, n2, d2); printf(" After: "); printArray(arr2, n2); /* Case 3: Single element */ int arr3[] = {42}; printf("\nCase 3: Single element\n"); printf(" Before: "); printArray(arr3, 1); rotateReversal(arr3, 1, 3); printf(" After: "); printArray(arr3, 1); /* Case 4: d = n */ int arr4[] = {1, 2, 3, 4}; printf("\nCase 4: d = n (no change)\n"); printf(" Before: "); printArray(arr4, 4); rotateReversal(arr4, 4, 4); printf(" After: "); printArray(arr4, 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 Rotation Approaches

1. One by One: Simple, O(n × d) time — inefficient for large d.
2. Temporary Array: O(n) time, O(n) space — simple and fast.
3. Juggling: O(n) time, O(1) space — uses GCD cycles.
4. Reversal: O(n) time, O(1) space — elegant and efficient.

Expected Output (sample run)

text

=== Array Rotation (Right/Clockwise) Demo === --- Menu --- 1. Demonstrate All Approaches 2. Custom Rotation 3. Performance Comparison 4. Edge Cases 5. Exit Enter choice: 1 === All Rotation Approaches === Original: [1, 2, 3, 4, 5, 6], d = 2 Expected: [5, 6, 1, 2, 3, 4] One by One: [5, 6, 1, 2, 3, 4] Verify: PASS Temp Array: [5, 6, 1, 2, 3, 4] Verify: PASS Juggling: [5, 6, 1, 2, 3, 4] Verify: PASS Reversal: [5, 6, 1, 2, 3, 4] Verify: PASS --- Menu --- ... Enter choice: 3 === Performance Comparison (n = 100000, d = 12345) === Temp Array: 0.834 ms Juggling: 0.612 ms Reversal: 0.578 ms --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: d = 0 Before: [1, 2, 3, 4, 5] After: [1, 2, 3, 4, 5] Case 2: d = 4 > n = 3 (d % n = 1) Before: [1, 2, 3] After: [3, 1, 2] Case 3: Single element Before: [42] After: [42] Case 4: d = n (no change) Before: [1, 2, 3, 4] After: [1, 2, 3, 4]

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Not Handling d > n

Forgetting d %= n causes incorrect or excessive rotations.

c

void rotate(int arr[], int n, int d) { /* BUG: d might be > n */ }

Solution: Always apply d %= n at the start.

2. Negative d

Negative d causes undefined behavior with modulo.

c

d = -1; d %= n; /* Result is implementation-defined for negatives */

Solution: Convert negative to positive: d = ((d % n) + n) % n;

3. Empty Array

Rotating an empty array with n = 0 causes division by zero.

c

d %= n; /* BUG: n == 0 */

Solution: Check if (n <= 1) return; at the start.

4. Single Element

A single-element array is unchanged by rotation.

Solution: Early return for n <= 1.

5. Memory Leaks with Temporary Array

Forgetting to free the temporary array.

c

int *temp = malloc(n * sizeof(int)); /* ... */ /* Missing free(temp); */

Solution: Always free dynamically allocated memory.

6. Integer Overflow in Index Computation

(currIdx + d) % n may overflow for large values.

c

int nextIdx = (currIdx + d) % n; /* May overflow for very large d */

Solution: Use (currIdx + (d % n)) % n to keep values small.

7. Juggling Cycle Count

Incorrect cycle count (GCD) leads to incomplete rotation.

c

int cycles = d; /* BUG: should be gcd(n, d) */

Solution: Use gcd(n, d).

8. Reversal with d = 0

Reversing when d = 0 corrupts the array.

c

reverse(arr, 0, n - 1); /* BUG if d == 0 */

Solution: Early return when d % n == 0.

9. Off-by-One in Reversal Bounds

Incorrect bounds cause elements not to be reversed.

c

reverse(arr, 0, d); /* BUG: should be d - 1 */

Solution: Use reverse(arr, 0, d - 1) for first d elements.

10. Memory Considerations

• One-by-One: O(1) space, but slow for large d.
• Temporary Array: O(n) space, fast.
• Juggling: O(1) space, optimal for in-place.
• Reversal: O(1) space, simplest in-place.

---

Summary & Best Practices

Right array rotation is a fundamental operation with multiple efficient implementations. The reversal algorithm is the most elegant in-place solution; the temporary array is simplest for readability.

Key Takeaways

• Right rotation by d moves elements right; wrap-around occurs.
• Apply d %= n to handle d > n.
• One-by-One: O(n × d) time — simple but slow.
• Temporary Array: O(n) time, O(n) space — simple and fast.
• Juggling: O(n) time, O(1) space — uses GCD cycles.
• Reversal: O(n) time, O(1) space — elegant in-place.

Best Practices

1. Always apply d %= n to handle d > n.
2. Handle edge cases: empty array, single element, d = 0, d = n.
3. Use the reversal algorithm for in-place O(1) rotation.
4. Use the temporary array for clarity when space permits.
5. Free dynamically allocated memory in temporary array approach.
6. Prefer iterative approaches over recursion for stack safety.
7. Validate input (array size, d range).
8. Document whether rotation is left or right.
9. Test with odd and even array lengths.
10. Measure performance for very large arrays.

By mastering array rotation, you’ll have a powerful tool for circular data processing and algorithm design.