CODEWITHSUNDEEP
algorithm
Debarshi Dutta
Debarshi Dutta

Reputation: 442

How to determine the value at a position of a sorted array after K rotations?

Suppose I have an array of Size 4 and there are 5 elements 

1)  0,1,2,3
2)  4,0,1,2 after 1st rotation
3)  3,4,0,1 after 2nd rotation
4)  2,3,4,0 after 3rd rotation 
5)  1,2,3,4 after 4th rotation
6)  0,1,2,3 after 5th rotation

as we can see the number repeats itself after 5 iterations. Is there an efficient way to search for kth element of the array ? after say N rotations??

Upvotes: 1

Views: 111

Answers (2)

nameless
nameless

Reputation: 1979

Assume array indices are zero-based.

To compute the index of the Kth value of an M-element array after N rotations you should use the following expression

(K + N) mod M

So given an array arr, you should get the value like this (using C-like syntax):

arr[(K + N) % M];

Upvotes: 2

PearsonArtPhoto
PearsonArtPhoto

Reputation: 39718

The easiest thing to do would be to put the combinations in to some sort of an array, and directly index the number. It would probably be worth it to make sure the numbers are valid beforehand as well. I believe this will do (Assuming first row is 0, first column is 0, adjust if you want to change the start point by addition)

elements=[0,1,2,3,4]
out=elements((K-N)%5

Quick test:

N=1, K=3, out=2 correct
N=5, K=1, out=1 correct

Upvotes: 1

Related Questions