Arrays: Left Rotation
Problem Description
The problem was published on Hackerrank, you can find it here.
You are given an array of size n and an integer k. Return the array after performing k left rotations on it.
Example
5 2
1 2 3 4 5
We have an array of size 5, and we will perform 2 left rotations on it. A left rotation is taking an element on the left of the array and appending it to the right. Here is how we reach the answer:
After first rotation : 2 3 4 5 1
After second rotation : 3 4 5 1 2
You can already notice at this point that after n rotations, n being the array's length, we come back to the initial array because we completed a full rotation. This intuitive remark will be applied in our code later.
Problem Solution
Going through several examples with ordered arrays like 1 2 3 4 5 helps to understand the logic behind the solution. We already saw that rotating an n-length array n times gives the same array. This means that if k >= n, then applying k rotations is the same as appying k - n rotations. Let's focus on the problem if k < n then.
When k < n : take a step back and look at what we are doing. You pick the first element and add it and the end of the array, which means you keep the array order. After the k operations, the k first elements of the initial array will be at the end (which is array[0:k]) and the n-k elements will be at the front (which is array[k:n]). Remains to deal with k when k>n. We can take k_new such as k_new = k % n. Indeed we are removing the unnecessary rotations and k_new < n by definition.
We can write down the code and see that it passes all test cases
def array_left_rotation(a, n, k):
answer = a[k%n:n]+a[0:k%n]
n, k = map(int, input().strip().split(' '))
a = list(map(int, input().strip().split(' ')))
answer = array_left_rotation(a, n, k);
print(*answer, sep=' ')
print(array_left_rotation([1, 2, 3, 4, 5], 5, 2))
[3, 4, 5, 1, 2]
Written by Victor
Published