Rotate Array - C Solution

1. Introduction

This blog post discusses a common array manipulation problem in C programming - rotating an array. Rotation involves shifting elements of an array by a certain number of positions. This problem is a great way to understand array indexing and manipulation techniques, especially when dealing with circular data structures.

Problem

Given an integer array nums, the task is to rotate the array to the right by k steps, where k is non-negative. This means that each element of the array needs to be moved k positions to the right, with the elements at the end of the array wrapping around to the front.

2. Solution Steps

1. Normalize k to handle cases where k is larger than the array size.

2. Reverse the entire array.

3. Reverse the first k elements.

4. Reverse the remaining n-k elements.

5. The array is now rotated k times to the right.

3. Code Program

#include <stdio.h>

// Function to reverse a segment of the array from 'start' to 'end'
void reverse(int* nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

// Function to rotate the array to the right by 'k' steps
void rotate(int* nums, int numsSize, int k) {
    k %= numsSize; // Normalize k
    reverse(nums, 0, numsSize - 1); // Reverse the entire array
    reverse(nums, 0, k - 1);       // Reverse first k elements
    reverse(nums, k, numsSize - 1); // Reverse remaining n-k elements
}

// Main function to test the rotate function
int main() {
    int nums1[] = {1, 2, 3, 4, 5, 6, 7};
    int k1 = 3;
    int numsSize1 = sizeof(nums1) / sizeof(nums1[0]);
    rotate(nums1, numsSize1, k1);

    printf("Rotated array 1: ");
    for (int i = 0; i < numsSize1; i++) {
        printf("%d ", nums1[i]);
    }
    printf("\n");

    int nums2[] = {-1, -100, 3, 99};
    int k2 = 2;
    int numsSize2 = sizeof(nums2) / sizeof(nums2[0]);
    rotate(nums2, numsSize2, k2);

    printf("Rotated array 2: ");
    for (int i = 0; i < numsSize2; i++) {
        printf("%d ", nums2[i]);
    }
    printf("\n");

    return 0;
}

Output:

Rotated array 1: 5 6 7 1 2 3 4
Rotated array 2: 3 99 -1 -100

Explanation:

1. k %= numsSize; - Normalize k to be within the bounds of the array size.

2. reverse(nums, 0, numsSize - 1); - Reverse the entire array.

3. reverse(nums, 0, k - 1); - Reverse the first k elements.

4. reverse(nums, k, numsSize - 1); - Reverse the remaining n-k elements.

5. rotate function combines these steps to rotate the array.

6. The main function tests the rotate function with two examples and prints the rotated arrays.