Circular Array Rotation

Problem Statement of Circular Array Rotation challenge

Given array of size n is right rotated k times. Find out the element at i^th position in the resultant array. The original Circular Array Rotation problem statement is available on Hackerrank.

What is Right Rotation?

1 right rotation shifts all elements of array one position right and last element is shifted to first position. If this process is repeated k times then it is called k right rotations. Example is given below-

Observations

Case 1: k == n (size of the array)

Rotations will not have any effect on array. Original array will be restored.

Case 2: k > n (size of Array)

For example, if n = 10 and k = 15, then first 10 rotations will not have any effect on original array. Remaining 5 rotations will be effective. Therefore we can say only k % n rotations will be effective.

Which element reaches at i^th position after k rotations?

Case 1: i >= k

The element which is k positions behind i^th position will reach at i^th position after k right rotations. The element at index (i – k) will reach at index i after k right rotations. To consider only effective rotations we can write (i – k%n) instead of (i – k).

Case 2: i < k

For the indexes i < k, (i – k%n) will give negative index. Which means the element of such index actually comes from right side of this index. To adjust it we will add n (size of the array) to get the element from right. So the correct index will be (i – k%n + n).

Generalized Formula covering both of above cases

To save the time for separately determining both cases we can use (i – k%n + n)%n. Extra %n used at the end of the formula generated in case 2 will nullify the effect of adding n (+n) in the formula of case 1 (i – k%n) where i >= k. Otherwise it works fine for case 2 where i < k.

Suppose we want to generate the resultant array B in one go after k rotations of given array A, we can directly use following formula.

B[i] = A[(i – k%n + n)%n]

How to answer Queries of original problem?

Input array => [3, -5, 8, 7, 12, -9, 23, 9, 10, 50]
n = 10
k = 3

for i = 5
Required index of original array = (i – k%n + n)%n  =  (5 – 3%10 + 10)%10 = 2
A[2] = 8. 8 is the answer.

For i = 1
Required index of original array = (i – k%n + n)%n  =  (1 – 3%10 + 10)%10 = 8
A[8] = 10. 10 is the answer.

Time complexity of the solution is O(Q), where Q is number of queries. Each query is answered in O(1) time.

Recommended Posts-
Append and Delete
Insertion Sort Advanced Analysis
Organizing Containers of Balls
Can we ditch python for competitive coding?
5 C functions for competitive programming?
Prefix Sum : Query Time O(1) : Pre-processing Time O(n)