Cyclic Rotation – Coditility

Share on facebook
Share on google
Share on twitter
Share on linkedin
Let’s share three different ways to solve this problem and each solution will improve the previous one. The problem:
you get a big array of integers A and a number K as the amount of shifts to the right. Example:

arr = [1,2,3,4,5]
k = 2
//solution
[4,5,1,2,3]

like to the exercise
link to github code

First Solution

This version is just looping K times and pop and push to the start:

i = 0
while i < K:
  lastItem = arr.pop()
  arr.prepend(lastItem) # push to the start of the array
return arr

Second Solution

Quite similar to the previous one, but this time we calculate K to the min rotations needed. Lets say we have an array of [1,2,3], now if will have 3,6,9,12,….. rotations the array will stay in the exact order. That means we can cut all of those useless rotations with:

arrLength = len(arr)
newK = arrLength % K
# newK is what we loop over now
# so we may have saved a lot of useless rotations
i = 0
while i < newK:
  lastItem = arr.pop()
  arr.prepend(lastItem) # push to the start of the array
return arr

My Final Solution:

Instead of looping over the array and popping and pushing I can just split the array where I need and reconnect it. so we have this array: [1,2,3,4,5,6,7,8] and K=3 So the result should be [6,7,8,1,2,3,4,5] as you can see this is like joining these two arrays [6,7,8] [1,2,3,4,5] so the first array would be:
[arrLen - newK ...... arrLen]
and the second
[0 ...... arrLen-1] This is my solution (python)

def solution(arr , k):
    arrLen = len(arr)
    if arrLen == 0:
        return arr
    moves = k % arrLen
    return arr[arrLen-moves:arrLen] + arr[0:arrLen-1]