2.1 - Cyclic rotation (Problem of Arrays)

Cyclic Rotation

Problem

An 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 moved to the first place. For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7] (elements are shifted right by one index and 6 is moved to the first place).

The goal is to rotate array A K times; that is, each element of A will be shifted to the right K times.

Write a function:

def solution(A, K)

that, given an array A consisting of N integers and an integer K, returns the array A rotated K times.

Assume that:

N and K are integers within the range [0..100];

each element of array A is an integer within the range [−1,000..1,000].

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

Example

For example, given

A = [3, 8, 9, 7, 6]

K = 3

the function should return [9, 7, 6, 3, 8]. Three rotations were made:

[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]

[6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]

[7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]

For another example, given

A = [0, 0, 0]

K = 1

the function should return [0, 0, 0]

Given

A = [1, 2, 3, 4]

K = 4

the function should return [1, 2, 3, 4]

The Modulus Trick

Instead of writing code to move each element multiple times towards their final state, we move each element once to their final position.

We swap the elements using the following formula:

B[ (i+K) % len(A) ] = A[i]

Note: % is the modulus operator that basically returns the remainder from the division operation (as in long division method)

In Code

def solution(A, K):
    rtn = [0 for i in A]

    for i in range(len(A)):
        rtn[(i + K) % len(A)] = A[i]
    return rtn

Test Cases

print(solution([1,2,3], 1))

print(solution([3, 8, 9, 7, 6], 3))

print(solution([0, 0, 0], 1))

[3, 1, 2]

[9, 7, 6, 3, 8]

[0, 0, 0]

Other Test Case Types

-extreme_empty

empty array

-single

one element, 0 <= K <= 5

-double

two elements, K <= N

-small1

small functional tests, K < N

-small_random_all_rotations

small random sequence, all rotations, N = 15

-medium_random

medium random sequence, N = 100

-maximal

maximal N and K

Tags: Algorithms,Technology,