Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Arrays

Rotate Array Right by K

Easy · Arrays · Asked at Amazon, Microsoft, TCS, Infosys, Wipro

Rotate the array to the right by k steps: every element moves k places to the right and the ones that fall off the end wrap around to the front.

Input

First line: n k. Second line: n integers.

Output

The rotated array, space-separated.

Constraints

k can be larger than n — use k % n. The reversal trick does it in place: reverse all, then reverse the first k and the rest.

Example 1

Input

7 3
1 2 3 4 5 6 7

Output

5 6 7 1 2 3 4

Example 2

Input

2 5
-1 99

Output

99 -1

Hints

  1. Rotating by n gives the same array, so only k % n matters.
  2. Reverse the whole array, then reverse the first k elements and the remaining n − k separately.

Approach

Set k = k % n. The reversal trick rotates in place: reversing everything puts the last k elements at the front but backwards; reversing the first k and the last n − k fixes both parts. No extra array needed.

Complexity: O(n) time · O(1) extra space

Solution

C++ solution

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

int main() {
    long long n, k;
    cin >> n >> k;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    k %= n;
    reverse(a.begin(), a.end());
    reverse(a.begin(), a.begin() + k);
    reverse(a.begin() + k, a.end());
    for (int i = 0; i < n; i++) cout << a[i] << (i + 1 < n ? " " : "\n");
    return 0;
}

Python solution

import sys

data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = data[2 : 2 + n]
k %= n
print(*(a[n - k :] + a[: n - k]))

Java solution

import java.util.*;

public class Main {
    static void reverse(long[] a, int l, int r) {
        while (l < r) {
            long t = a[l];
            a[l++] = a[r];
            a[r--] = t;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        int s = (int) (k % n);
        reverse(a, 0, n - 1);
        reverse(a, 0, s - 1);
        reverse(a, s, n - 1);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) sb.append(a[i]).append(i + 1 < n ? " " : "");
        System.out.println(sb);
    }
}

Solve Rotate Array Right by K online · All practice problems