.

Wednesday, August 3, 2016

CyclicRotation Algo and Implementation in Python

A zero-indexed array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is also moved to the first place.
For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7]. The goal is to rotate array A K times; that is, each element of A will be shifted to the right by K indexes.
Implementation 1: Without using any inbuilt functionality

1
2
3
4
5
6
def solution(A, K):
    result = []
    length = len(A)
    for i in range(length):
        result.insert((abs((i + K) % length)), A[i])
    return result 


Implementation 2: Using Deque data structure

1
2
3
4
5
6
from collections import deque

def solution(A, K):
    items = deque(A)
    items.rotate(K)
    return list(items)


Implementation 2: One Liner solution

1
2
def solution(A, K):
    return A[-K % len(A):] + A[:-K % len(A)]

No comments :

Post a Comment