Getting everything ready for you…

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

0s

Practice › Arrays

Left Rotate by K

Easy · Arrays · Asked at TCS, Infosys, Wipro, Accenture, Cognizant

Rotate the array to the left by k positions and print it.

Input

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

Output

The rotated array, space-separated.

Constraints

k can be larger than n — use k % n. Bonus: do it with three reversals and O(1) extra space.

Example 1

Input

5
1 2 3 4 5
2

Output

3 4 5 1 2

Example 2

Input

3
1 2 3
3

Output

1 2 3

Hints

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

Approach

Set k = k % n. The three-reversal trick rotates in place: reverse a[0..k-1], reverse a[k..n-1], then reverse everything. For example [1 2 3 4 5] with k = 2 → [2 1 5 4 3] → [3 4 5 1 2]. Printing a[(i + k) % n] for each i is an equally valid O(n) answer.

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

Solution

C++ solution

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

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    long long k;
    cin >> k;
    k %= n;
    reverse(a.begin(), a.begin() + k);
    reverse(a.begin() + k, a.end());
    reverse(a.begin(), 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 = int(data[0])
a = data[1 : n + 1]
k = int(data[n + 1]) % n
print(*(a[k:] + a[:k]))

Java solution

import java.util.*;

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

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

Solve Left Rotate by K online · All practice problems