Find last element of Array by rotating and deleting N-K+1 element – GeeksforGeeks

Given an array arr[] of N integers, the task is to find the element which is left at last after performing the following operation N – 1 time. For everyone K^th operation:

• Right-rotate the array clockwise by 1.
• Delete the (n – K + 1)^th last element.

Example:

input: N = 6, arr[] = {1, 2, 3, 4, 5, 6}
Output: 3
Explanation: Rotate the array clockwise ie after rotation the array A = {6, 1, 2, 3, 4, 5} and delete the last element that is {5} that will be A = {6, 1, 2, 3, 4} .
Again rotate the array for the second time and deletes the second last element that is {2} that will be A = {4, 6, 1, 3}, doing a similar operation when we perform the 4th operation, the 4th last element does not exist. Then we delete 1st element ie {1} that will be A = {3, 6}. So, continuing this procedure the last element in A is {3}.
So, the output will be 3.

input: N = 4, arr = {1, 2, 3, 4}
Output: 3

Approach: To solve the problem follow the steps as mentioned:

Do N – 1 operation and for each operation Right rotate the array clockwise by 1 and Delete the (N – K + 1)^th last element then finally return the first element which left in the array.

Follow the steps below to implement the above idea:

• Initialize a variable K = 1, for counting the number of operations done until now
• Do while K is less than the size of the array.
  • Do right rotation
  • Erase the N – K + 1 element
  • Update the current size of the array
  • Increase the value of K by 1
• Return the first left element of the array.

Below is the implementation of the above approach:

Time complexity: O(N²)
Auxiliary Space: O(1)