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 every Kth 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 i.e. 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 similar operation when we perform 4th operation, 4th last element does not exist. Then we deletes 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 till 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
- Increment the value of K by 1
- Return the first left element of the array.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the last remaining elementint rotateDelete(vector<long long>& v, int n){ // Initialise a variable K = 1, for // counting the number of operations // done till now int k = 1; while (k < n) { // Clockwise rotation rotate(v.begin(), v.begin() + v.size() - 1, v.end()); // Erase the n - k + 1 element v.erase(v.begin() + n - k); // Update the current size of array n = v.size(); // Increment the value of K k++; } // Return the first left element // of the array. return v[0];}// Driver codeint main(){ vector<long long> arr = { 1, 2, 3, 4, 5, 6 }; int N = arr.size(); // Function call cout << rotateDelete(arr, N); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG{ // Function to find the last remaining element public static int rotateDelete(ArrayList<Integer> v, int n) { // Initialise a variable K = 1, for // counting the number of operations // done till now int k = 1; while (k < n) { // Clockwise rotation Collections.rotate(v, 1); // Erase the n - k + 1 element v.remove(v.size() - k); // Update the current size of array n = v.size(); // Increment the value of K k++; } // Return the first left element // of the array. return v.get(0); } // Driver Code public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<Integer>(); arr.add(1); arr.add(2); arr.add(3); arr.add(4); arr.add(5); arr.add(6); int N = arr.size(); // Function call System.out.print(rotateDelete(arr, N)); }}// This code is contributed by Rohit Pradhan |
Python3
# Function to find the last remaining elementdef rotateDelete(v, n): # Initialise a variable K = 1, for # counting the number of operations # done till now k = 1 while (k < n): # Clockwise rotation v = v[len(v) - 1:len(v)] + v[0:len(v) - 1] # Erase the n - k + 1 element v.pop(n-k) # Update the current size of array n = len(v) # Increment the value of K k += 1 # Return the first left element # of the array. return v[0]arr = [1, 2, 3, 4, 5, 6]N = len(arr)# Function callprint(rotateDelete(arr, N))# This code is contributed by vikkycirus |
C#
// C# implementationusing System;using System.Linq;using System.Collections.Generic;public class GFG { // Function to rotate array public static void rotate(int[] arr, int d, int n) { // Storing rotated version of array int[] temp = new int[n]; // Keeping track of the current index // of temp[] var k = 0; // Storing the n - d elements of // array arr[] to the front of temp[] for (int i = d; i < n; i++) { temp[k] = arr[i]; k++; } // Storing the first d elements of array arr[] // into temp for (int i = 0; i < d; i++) { temp[k] = arr[i]; k++; } // Copying the elements of temp[] in arr[] // to get the final rotated array for (int i = 0; i < n; i++) { arr[i] = temp[i]; } } // Function to find the last remaining element public static int rotateDelete(int[] v, int n) { // Initialise a variable K = 1, for // counting the number of operations // done till now int k = 1; while (k < n) { // Clockwise rotation int l = v.Length; rotate(v, l - 1, l); // Erase the n - k + 1 element List<int> nums = new List<int>(v); nums.RemoveAt(n - k); v = nums.ToArray(); // Update the current size of array n = v.Length; // Increment the value of K k++; } // Return the first left element // of the array. return v[0]; } static public void Main() { int[] arr = { 1, 2, 3, 4, 5, 6 }; int N = arr.Length; // Function call Console.WriteLine(rotateDelete(arr, N)); }}// This code is contributed by ksam24000 |
Javascript
function Rotate(arr,d,n) { // Initializing array temp with size n var temp=new Array(n); let k = 0; // Storing the n - d elements of // array arr[] to the front of temp[] for (let i = d; i < n; i++) temp[k++] = arr[i]; // Storing the first d elements of array arr[] // into temp for (let i = 0; i < d; i++) temp[k++] = arr[i]; for(let i=0;i<arr.length;i++) arr[i]=temp[i]; }// Function to find the last remaining elementfunction rotateDelete( v, n){ // Initialise a variable K = 1, for // counting the number of operations // done till now let k = 1; while (k < n) { // Clockwise rotation Rotate(v,v.length-1,v.length); // Erase the n - k + 1 element v.splice(n-k, 1) // Update the current size of array n = v.length; // Increment the value of K k++; } // Return the first left element // of the array. return v[0];}// Driver code let arr = [ 1, 2, 3, 4, 5, 6 ]; let N = arr.length; // Function call console.log(rotateDelete(arr, N));// This code is contributed by garg28harsh. |
PHP
<?php// Function to find the last remaining elementfunction rotateDelete($v, $n){ // Initialise a variable K = 1, for // counting the number of operations // done till now $k = 1; while ($k < $n) { // Clockwise rotation $lastElement = array_pop($v); array_unshift($v, $lastElement); // Erase the n - k + 1 element array_splice($v, $n - $k, 1); // Update the current size of array $n = count($v); // Increment the value of K $k++; } // Return the first left element // of the array. return $v[0];}// Driver code$arr = array(1, 2, 3, 4, 5, 6);$N = count($arr);// Function callecho rotateDelete($arr, $N);// This code is contributed by Kanishka Gupta?> |
Output
3
Time complexity: O(N2)
Auxiliary Space: O(1)
Take a part in the ongoing discussion
