YouTipC Exercise Example68
# C Programming Exercise - Array Rotation (Example 68)
In this tutorial, you will learn how to rotate an array of $n$ integers to the right by $m$ positions. This is a classic array manipulation problem that helps build a solid understanding of array indexing, memory management, and pointer operations in C.
---
## 1. Problem Description
Given an array of $n$ integers, shift all elements to the right by $m$ positions. The last $m$ elements that "fall off" the end of the array must wrap around and become the first $m$ elements of the array.
### Example
* **Input Array:** `[1, 2, 3, 4, 5, 6, 7]` (where $n = 7$)
* **Shift Value ($m$):** `3`
* **Output Array:** `[5, 6, 7, 1, 2, 3, 4]`
---
## 2. Algorithm Analysis
There are multiple ways to solve this problem. Two common approaches are:
### Method 1: Using an Auxiliary Array (Temporary Buffer)
1. Create a temporary array of size $m$ to store the last $m$ elements of the original array.
2. Shift the remaining $n - m$ elements of the original array to the right by $m$ positions.
3. Copy the $m$ elements from the temporary array back to the beginning of the original array.
### Method 2: In-Place Reversal (Optimal Space Complexity)
If you want to rotate the array in-place with $O(1)$ extra space, you can use the **reversal algorithm**:
1. Reverse the entire array.
2. Reverse the first $m$ elements.
3. Reverse the remaining $n - m$ elements.
*(Note: In this tutorial, we will focus on the auxiliary array approach and pointer-based implementations as shown in the classic examples).*
---
## 3. Code Implementations
### Solution 1: Using a Temporary Array (VLA Approach)
This solution uses a Variable-Length Array (VLA) to temporarily store the elements that wrap around.
```c
#include
// Function to shift array elements to the right by m positions
void shiftArray(int arr[], int n, int m) {
// Handle cases where m is larger than n
m = m % n;
int temp;
// 1. Save the last m elements into the temporary array
for (int i = n - m, j = 0; i < n; i++, j++) {
temp = arr;
}
// 2. Shift the first n - m elements backward by m positions
for (int i = n - m - 1; i >= 0; i--) {
arr[i + m] = arr;
}
// 3. Copy the temporary array elements back to the front
for (int i = 0; i < m; i++) {
arr = temp;
}
}
int main() {
int n, m;
printf("Enter the number of elements (n): ");
if (scanf("%d", &n) != 1 || n <= 0) {
printf("Invalid array size.\n");
return 1;
}
printf("Enter the shift offset (m): ");
if (scanf("%d", &m) != 1 || m < 0) {
printf("Invalid shift offset.\n");
return 1;
}
int arr;
printf("Enter %d integers:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr);
}
// Perform rotation
shiftArray(arr, n, m);
// Print the rotated array
printf("Rotated array:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr);
}
printf("\n");
return 0;
}
```
---
### Solution 2: Pointer-Based Array Rotation
This solution demonstrates how to structure your code with modular helper functions for printing and shifting. It uses a fixed-size array buffer for safety.
```c
#include
#include
// Function declarations
void print_arr(int array[], int n);
void move(int array[], int n, int offset);
int main() {
int arr;
int i, n, offset;
// Input array size
printf("Total numbers? (Max 20):\n");
if (scanf("%d", &n) != 1 || n > 20 || n <= 0) {
printf("Invalid size.\n");
return 1;
}
// Input array elements
printf("Input %d numbers:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr);
}
// Input rotation offset
printf("Set your offset:\n");
scanf("%d", &offset);
printf("Offset is %d.\n", offset);
// Print array before rotation
printf("Original array:\n");
print_arr(arr, n);
// Rotate and print the array
move(arr, n, offset);
printf("Rotated array:\n");
print_arr(arr, n);
return 0;
}
// Helper function to print array elements
void print_arr(int array[], int n) {
int i;
for (i = 0; i < n; ++i) {
printf("%4d", array);
}
printf("\n");
}
// Function to shift array elements using a temporary buffer
void move(int array[], int n, int offset) {
offset = offset % n; // Normalize offset if it is larger than n
if (offset == 0) return;
int *temp = (int *)malloc(offset * sizeof(int));
if (temp == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
// Copy the last 'offset' elements to temp
for (int i = 0; i < offset; i++) {
temp = array[n - offset + i];
}
// Shift the remaining elements to the right
for (int i = n - 1; i >= offset; i--) {
array = array;
}
// Copy temp elements back to the front
for (int i = 0; i < offset; i++) {
array = temp;
}
free(temp); // Free allocated memory
}
```
---
## 4. Key Considerations & Edge Cases
When implementing array rotation in production environments, keep the following points in mind:
1. **Offset Normalization (`m % n`):**
If the shift offset $m$ is greater than the array size $n$, shifting by $m$ is equivalent to shifting by `m % n`. Always normalize the offset to prevent out-of-bounds memory access.
2. **Memory Management:**
If using dynamic memory allocation (`malloc`), always check if the pointer returned is `NULL` and ensure you call `free()` to prevent memory leaks.
3. **Variable-Length Arrays (VLAs):**
VLAs (e.g., `int temp` where `m` is a variable) are supported in C99 but became optional in C11. For maximum cross-compiler compatibility, use dynamic memory allocation (`malloc`/`free`) or a fixed-size buffer.