C program to rotate an array left and right by a given number K

In this blog post, we learn how to write a C program to rotate an array left and right by a given number K? So here we will write a C program to rotate an array left and right by a given number K.

Suppose ‘arr’ is an integer array of size N and task to rotate the array to the left or right by k steps, where k is non-negative. Here, array rotation means shifting the array elements to the left or right of the array by specified positions.

Example,

Input: int arr[] = {1,2,3,4,5,6,7}, k = 3

Output: {5,6,7,1,2,3,4}

Explanation:

rotate 1 steps to the right-> {7,1,2,3,4,5,6}
rotate 2 steps to the right-> {6,7,1,2,3,4,5}
rotate 3 steps to the right-> {5,6,7,1,2,3,4}

Let’s see some solution to rotate an array left and right by a given number K. But it would be great if you try to solve this problem yourself first.

Solution 1:

In this solution, first, we will create two functions to shift the array element one position to left and right. After creating these two functions we call them in other functions where they will be called in the loop according to the value of ‘k’.

In the one left shift function, we will create an intermediate temp variable to store the first element ( arr[0] ) array. Now we will move arr[1] to arr[0], arr[2] to arr[1] …and finally temp to arr[n-1]. This technique will rotate the array element 1 position.

In the right shift, we need to store the last element of the array in the temp variable and move the arr[n-2] to arr[n-1], arr[n-3] to arr[n-2] …and finally temp to arr[0].

If you want to learn more about the C language, you can check this course, Free Trial Available.

Get Your Free Trial

Let’s see the c program to left and right rotate array elements by kth position.

#include <stdio.h>
#include <stdint.h>

//Calculate array size
#define ARRAY_SIZE(arr)  sizeof(arr)/sizeof(arr[0])


// Function to right-rotate an array by one position
void rightRotateByOne(int arr[], int arr_size)
{
    int i;
    //take last element of the array
    int last = arr[arr_size - 1];
    for (i = arr_size - 2; i >= 0; i--)
    {
        arr[i + 1] = arr[i];
    }
    // Now store the last element
    // at 0th index of the array
    arr[0] = last;
}

// Function to left-rotate an array by one position
void leftRotatebyOne(int arr[], int arr_size)
{
    //get first element of the array
    int first = arr[0], i;
    for (i = 0; i < arr_size - 1; i++)
    {
        arr[i] = arr[i + 1];
    }

    arr[i] = first;
}


//Function to left rotate an array by 'k' positions
void leftRotate(int arr[], int k, int arr_size)
{
    int i;
    for (i = 0; i < k; i++)
    {
        leftRotatebyOne(arr, arr_size);
    }
}


// Function to right-rotate an array by 'k' positions
void rightRotate(int arr[], int k, int arr_size)
{
    int i;
    for (i = 0; i < k; i++)
    {
        rightRotateByOne(arr, arr_size);
    }
}




//print the array elements
void printArray(int arr[], int arr_size)
{
    int i;
    for (i = 0; i < arr_size; i++)
    {
        printf("%d ", arr[i]);
    }

    printf("\n\n");
}



int main()
{
    //array must be sorted
    int arr[] = {8, 11, 13, 15, 1, 4, 6};

    //get array size
    int arr_size = ARRAY_SIZE(arr);

    printf("Original Array = ");
    printArray(arr, 7);

    printf("Left shift array by 2 = ");
    leftRotate(arr, 2, arr_size);
    printArray(arr, 7);


    printf("Right shift array by 2 = ");
    rightRotate(arr, 2, arr_size);
    printArray(arr, 7);

    return 0;
}
rotate an array by kth position

Solution 2 (Juggling Algorithm):

In this solution besides the rotate the element one by one we will rotate the array in sets. Where the number of sets is equal to GCD of n (array size) and K (position to rotate array elements).

Suppose arr is an integer array and size is 7, we want to rotate it by 2.  So here n=7 and k =2 and array elements are {1,2,3,4,5,6,7};

If we calculate GCD of 7 and 2, then it would be 1. So elements will be moved within one set only, we just start with temp = arr[0] and keep moving arr[I+d] to arr[I] and finally store temp at the right place.

#include <stdio.h>
#include <stdint.h>

//Calculate array size
#define ARRAY_SIZE(arr)  sizeof(arr)/sizeof(arr[0])


//Calculate the calculateGcd
int calculateGcd(int a, int b)
{
    if (b == 0)
    {
        return a;
    }
    else
    {
        return calculateGcd(b, a % b);
    }
}

//Function to left rotate array of size n by k
void leftRotate(int arr[], int k, int n)
{
    int i, a, b, temp;
    // To handle if k >= n
    k = k % n;
    const int gcd = calculateGcd(k, n);
    for (i = 0; i < gcd; i++)
    {
        /* move i-th values of blocks */
        temp = arr[i];
        a = i;
        while (1)
        {
            b = a + k;
            if (b >= n)
                b = b - n;
            if (b == i)
                break;
            arr[a] = arr[b];
            a = b;
        }
        arr[a] = temp;
    }
}

//print array elements
void printArray(int arr[], int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
}


int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7};

    //get array size
    int arr_size = ARRAY_SIZE(arr);

    printf("Original Array = ");
    printArray(arr, arr_size);

    printf("Left shift array by 2 = ");
    leftRotate(arr, 2, arr_size);
    printArray(arr, arr_size);

    return 0;
}

Output: 3 4 5 6 7 1 2

Recommended Articles for you: