instagram

Find an element in array after rotating an array by k steps to the right

Rotate an array of n elements to the right by k steps and then find an element at particular position in array.

For example, with n = 5 and k = 3, the array [1,2,3,4,5] is rotated to [4,5,1,2,3]. Now after rotation we need element at position 3 which is 2

Consider this array as a circle and take one pointer P which is pointing to start of the array, Initially pointer is pointing to P = 0, Find below image for more details.

Now we want to rotate an array by k = 3 steps, Lets assume instead of rotating entire array we will just change the pointer to P = 3

NOTE: Now size of an array is 5 and if we rotate an array by 10 or 15 or 20 .. steps then our pointer will be at initial position P = 0,

Lets see what is the position of our pointer after k steps.

POINTER = K % SIZE;

Now to find an element at particular position in array we will use below equation.

ELEMENT = array[POINTER+POSITION] // HERE WE MIGHT GET ARRAY_OUT_OF_BOUND exception,

But what if pointer = 3 and position is also 3 then in above code we will get arrayOutOfBoundException, To avoid this we will use % SIZE it means we are continually rotating our pointer in circle. Thats the reason I asked to consider it as a circle not an array.

ELEMENT = array[(POINTER+POSITION)%SIZE]

Find entire algorithm below.

Share