Array Rotation

Last Updated on March 28, 2022 by Ria Pathak

CONCEPTS USED:

Basic Mathematics

DIFFICULTY LEVEL:

Medium

PROBLEM STATEMENT(SIMPLIFIED):

With a given array of size N and steps K, we have to print the array after K rotations to the right.

See original problem statement here

For Example:

Input: 

N = 5, K = 2
A[] = [1, 2, 3, 4, 5]

Output: 

[4, 5, 1, 2, 3]

Explanation: 

We are supposed to right rotate the array by 2 steps, so each element is shifted to the right by 2 places and elements at the end of the array will be shifted to the starting indexes of the array in a fashion similar to circular arrays.  

NOTE : Don’t forget to K = K % N, as K can be greater than N.

SOLVING APPROACH:

BRUTE FORCE METHOD

1. Naive solution would be to shift the array K times one by one.
2. Write a function that shifts all the elements by one place to the right.
3. Run a loop K times and execute this function.
4. Time Complexity of this solution will be O(K*N).

SOLUTIONS:

#include <stdio.h>

void rotate_by_one(int arr[],int n)
{
    int temp = arr[n-1];
    int i;
    for(i=n-1;i>0;i--)
    {
      arr[i]=arr[i-1];
    }
    arr[i] = temp;
}

int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
      int n,k;
      scanf("%d%d",&n,&k);
      k%=n;
      int arr[n];
      for(int i=0;i<n;i++)
        scanf("%d",&arr[i]);

      for(int i=0;i<k;i++)
      {
        rotate_by_one(arr,n);
      }

      for(int i=0;i<n;i++)
        printf("%d ",arr[i]);
      printf("\n");
  }

  return 0;
}

#include <bits/stdc++.h>
using namespace std;

void rotate_by_one(int arr[],int n)
{
  int temp = arr[n-1];
  int i;
  for(i=n-1;i>0;i--)
  {
    arr[i]=arr[i-1];
  }
  arr[i] = temp;
}

int main()
{
  int t;cin>>t;
  while(t--)
  {
    int n,k;cin>>n>>k;
    k%=n;
    int arr[n];
    for(int i=0;i<n;i++)
      cin>>arr[i];

    for(int i=0;i<k;i++)
    {
      rotate_by_one(arr,n);
    }

    for(int i=0;i<n;i++)
      cout<<arr[i]<<" ";
    cout<<"\n";
  }

  return 0;
}

Time Complexity: O(N*K)

Space Complexity: O(1)

EFFICIENT METHOD:

1. Each and every element is shifting towards right by a given step number.

2. This implies that an element sitting at ith position will be shifted to (i+k)^th position or in other words the element sitting at the (i-k)^th position will come to the i^th position.

3. But remember one thing adding current index value to the step number may result in pointing to a number that is greater than the array length or an array out of bound exception may occur.

4. For this scenario, we will take modulus of the obtained number i.e. (i+k)%N with the array length so that it will remain in the valid array locations.

5. For current location, element present at the (i-k+N)%N will be shifted to the current location.

6. N is additionally added to the formula in order to avoid modulus of negative number. But the result would be similar.

SOLUTIONS:

#include <stdio.h>

int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    int n,k;
    scanf("%d %d",&n,&k);
    k%=n;
    int arr[n],temp_arr[n];
    for(int i=0;i<n;i++)
      scanf("%d",&arr[i]);

    for(int i=n-1;i>=0;i--)
    {
      temp_arr[i] = arr[(i-k+n)%n];
    }
    for(int i=0;i<n;i++)
      printf("%d ",temp_arr[i]);
    printf("\n");
  }

  return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int t;cin>>t;
  while(t--)
  {
    int n,k;cin>>n>>k;
    k%=n;
    int arr[n],temp_arr[n];
    for(int i=0;i<n;i++)
      cin>>arr[i];

    for(int i=n-1;i>=0;i--)
    {
      temp_arr[i] = arr[(i-k+n)%n];
    }
    for(int i=0;i<n;i++)
      cout<<temp_arr[i]<<" ";
    cout<<"\n";
  }

  return 0;
}

import java.util.*;
import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while(t!=0)
    {
      int n = sc.nextInt();
      int k = sc.nextInt();
      k%=n;
      int arr[] = new int[n];
      int temp_arr[] = new int[n];
      for(int i=0;i<n;i++)
        arr[i] = sc.nextInt();

      for(int i=n-1;i>=0;i--)
      {
        temp_arr[i] = arr[(i-k+n)%n];
      }
      for(int i=0;i<n;i++)
        System.out.print(temp_arr[i] + " ");
      System.out.println();
      t--;
    }

  }
}

Space Complexity: O(N), for creating Temporary Array to store results.

This article tried to discuss Basic Mathematics. Hope this blog helps you understand and solve the problem. To practice more problems on backtracking you can check out MYCODE | Competitive Programming.