Problem Statement of Circular Array Rotation challenge
Given array of size n is right rotated k times. Find out the element at ith 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-
Given Array A[n]: n = 10 –>
Array after k right rotation for k = 1 (1 right rotation) –>
Array after k right rotations for k = 3 –>
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 ith position after k rotations?
Case 1: i >= k
The element which is k positions behind ith position will reach at ith 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]
Array B for k = 3 –>
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 = 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 = 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.
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)