Given an array Arr of length N, it is reduced by 1 element at each step. Maximum and Minimum elements will be removed in alternating order from the remaining array until a single element is remaining in the array. The task is to find the remaining element in the given array.
Examples:
Input: arr[] = {1, 5, 4, 2}
Output: 2
Explanation:
Remove Max element i.e., 5 arr[] = {1, 4, 2}
Remove Min element i.e., 1 arr[] = {4, 2}
Remove Max element i.e., 4 arr[] = {2}Input: arr[] = {5, 10}
Output: 5
Approach:
Follow the below idea to solve the problem:
The idea is to sort the array and return the middle element as all of the right and left elements will be removed in the process.
Follow the below steps to solve this problem:
- If N =1, return arr[0]
- Sort the array arr[]
- Return the middle element of the array i.e., arr[(N-1)/2]
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 element left int lastRemaining(int arr[], int N) { // If single element in array if (N == 1) return arr[0]; // Sort the array sort(arr, arr + N); // return middle element return arr[(N - 1) / 2]; } // Driver Code int main() { int arr[] = { 1, 5, 4, 2 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call cout << lastRemaining(arr, N) << endl; return 0; } |
Java
// Java code to implement the approach import java.util.*; class GFG { // Function to find the element left static int lastRemaining(int arr[], int N) { // If single element in array if (N == 1) return arr[0]; // Sort the array Arrays.sort(arr); // return middle element return arr[(N - 1) / 2]; } // Driver Code public static void main(String[] args) { int arr[] = { 1, 5, 4, 2 }; int N = arr.length; // Function call System.out.print(lastRemaining(arr, N)); } } // This code is contributed by sanjoy_62. |
Python3
# Python code to implement the approach # Function to find the element left def lastRemaining(arr, N): # If single element in array if (N == 1): return arr[0] # Sort the array arr.sort() # return middle element return arr[(N - 1) // 2] # Driver Code arr = [ 1, 5, 4, 2 ] N = len(arr) # Function call print(lastRemaining(arr, N)) # This code is contributed by athakur42u. |
C#
// C# code to implement the approach using System; class GFG { // Function to find the element left static int lastRemaining(int[] arr, int N) { // If single element in array if (N == 1) return arr[0]; // Sort the array Array.Sort(arr); // return middle element return arr[(N - 1) / 2]; } // Driver code public static void Main(string[] args) { int[] arr = { 1, 5, 4, 2 }; int N = arr.Length; // Function call Console.Write(lastRemaining(arr, N)); } } // This code is contributed by code_hunt. |
Javascript
<script> // JS code to implement the approach // Function to find the element left function lastRemaining(arr, N) { // If single element in array if (N == 1) return arr[0]; let x = Math.floor((N - 1) / 2); // Sort the array arr.sort(function (a, b) { return a - b }) // return middle element return arr[x]; } // Driver Code let arr = [1, 5, 4, 2]; let N = arr.length; // Function call document.write(lastRemaining(arr, N)); // This code is contributed by lokeshpotta20. </script> |
2
Time Complexity: O(N * log(N)), for sorting the given array of size N.
Auxiliary Space: O(1), as constant extra space is required.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
