TzookB

Cyclic Rotation – Coditility

Sat Jun 08 2019

Lets 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 exerciselink 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]