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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
package com.omt.learn.algo; public class RotateArrayByElement { public static void main(String[] args) { int a[] = {1,2,3,4,5}; int numberOfElementRotation = 3; int findIntAtPosition = 3; // Starts with 0 System.out.println(elementAtAfterRotation(a, numberOfElementRotation, findIntAtPosition)); } public static int elementAtAfterRotation(int[] a,int rotation, int position) { int size = a.length; int pointer = rotation % size; int element = a[((pointer+position)%size)]; return element; } } |
