Quick Links

## Problem Statement of Circular Array Rotation challenge

Given array of size ** n** is right rotated

**times. Find out the element at**

*k***position in the resultant array. The original**

*i*^{th}**problem statement is available on Hackerrank.**

*Circular Array Rotation*## 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 *–>

## 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

*, then first*

**k = 15***rotations will not have any effect on original array. Remaining*

**10****rotations will be effective. Therefore we can say only**

*5***rotations will be effective.**

*k % n*## Which element reaches at *i*^{th} position after *k* rotations?

^{th}

### Case 1: *i >= k*

The element which is ** k** positions behind

**position will reach at**

*i*^{th}**position after**

*i*^{th}**right rotations. The element at index**

*k***will reach at index**

*(i – k)***after**

*i**right rotations. To consider only effective rotations we can write*

**k***instead of*

**(i – k%n)***.*

**(i – k)**### Case 2: *i < k*

For the indexes** i < k**,

*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*

**(i – k%n)***(size of the array) to get the element from right. So the correct index will be*

**n****.**

*(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

*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 (*

**+n***) where*

**i – k%n***. Otherwise it works fine for case 2 where*

**i >= k***.*

**i < k**Suppose we want to generate the resultant array ** B** in one go after

**rotations of given array**

*k***, we can directly use following formula.**

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

Array * A*–>

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[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

**is number of queries. Each query is answered in**

*Q**time.*

**O(1)**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)