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

November 10, 2017 by omt

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.

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;
	}
	
	
	

}

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;

}