Remaining array element after repeated removal of the smallest element from pairs with absolute difference of 2 or 0
Given an array arr[] consisting of N positive integers, the task is to check if it is possible to reduce the size of the array to 1 by repeatedly removing the smallest element from a pair having absolute difference of 2 or 0 between them. If it is not possible to reduce, then print “-1”. Otherwise, print the last remaining element in the array.
Examples:
Input: arr[] = {2, 4, 6, 8, 0, 8}
Output: 8
Explanation:
arr[] = {2, 4, 6, 8, 0, 8}, Remove 0 from the pair (2, 0).
arr[] = {2, 4, 6, 8, 8}. Remove 2 from the pair (2, 4).
arr[] = {4, 6, 8, 8}, Remove 4 from the pair (4, 6).
arr[] = {6, 8, 8}. Remove 6 from the pair (6, 8).
arr[] = {8, 8}. Remove 8.
arr[] = {8}Input: arr[] = {1, 7, 3, 3}
Output: -1
Explanation:
arr[] = {1, 7, 3, 3}. Remove 1 from the pair (1, 3).
arr[] = {7, 3, 3}. Remove 3 from the pair (3, 3).
arr[] = {7, 3}. No more removals possible.
Approach: Follow the steps below to solve the problem:
- Sort the given array in ascending order.
- Traverse the array starting from the smallest element and check if there exists any pair of the adjacent elements having absolute difference other than 2 or 0 or not.
- If found to be true, then print “-1”. Otherwlse, print the largest element present in the array as that will be the only remaining array element after performing the given operations.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the last remaining // array element after repeatedly removing // the smallest from pairs having absolute // difference 2 or 0 void findLastElement( int arr[], int N) { // Sort the given array in // ascending order sort(arr, arr + N); int i = 0; // Traverse the array for (i = 1; i < N; i++) { // If difference between // adjacent elements is // not equal to 0 or 2 if (arr[i] - arr[i - 1] != 0 && arr[i] - arr[i - 1] != 2) { cout << "-1" << endl; return ; } } // If operations can be performed cout << arr[N - 1] << endl; } // Driver Code int main() { int arr[] = { 2, 4, 6, 8, 0, 8 }; int N = sizeof (arr) / sizeof (arr[0]); findLastElement(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find the last remaining // array element after repeatedly removing // the smallest from pairs having absolute // difference 2 or 0 static void findLastElement( int arr[], int N) { // Sort the given array in // ascending order Arrays.sort(arr); int i = 0 ; // Traverse the array for (i = 1 ; i < N; i++) { // If difference between // adjacent elements is // not equal to 0 or 2 if (arr[i] - arr[i - 1 ] != 0 && arr[i] - arr[i - 1 ] != 2 ) { System.out.println( "-1" ); return ; } } // If operations can be performed System.out.println( arr[N - 1 ]); } // Driver Code public static void main(String[] args) { int arr[] = { 2 , 4 , 6 , 8 , 0 , 8 }; int N = arr.length; findLastElement(arr, N); } } // This code is contributed by code_hunt. |
Python3
# Python program for the above approach # Function to find the last remaining # array element after repeatedly removing # the smallest from pairs having absolute # difference 2 or 0 def findLastElement(arr, N): # Sort the given array in # ascending order arr.sort(); i = 0 ; # Traverse the array for i in range ( 1 , N): # If difference between # adjacent elements is # not equal to 0 or 2 if (arr[i] - arr[i - 1 ] ! = 0 \ and arr[i] - arr[i - 1 ] ! = 2 ): print ( "-1" ); return ; # If operations can be performed print (arr[N - 1 ]); # Driver Code if __name__ = = '__main__' : arr = [ 2 , 4 , 6 , 8 , 0 , 8 ]; N = len (arr); findLastElement(arr, N); # This code is contributed by 29AjayKumar. |
C#
// C# program for the above approach using System; public class GFG { // Function to find the last remaining // array element after repeatedly removing // the smallest from pairs having absolute // difference 2 or 0 static void findLastElement( int []arr, int N) { // Sort the given array in // ascending order Array.Sort(arr); int i = 0; // Traverse the array for (i = 1; i < N; i++) { // If difference between // adjacent elements is // not equal to 0 or 2 if (arr[i] - arr[i - 1] != 0 && arr[i] - arr[i - 1] != 2) { Console.WriteLine( "-1" ); return ; } } // If operations can be performed Console.WriteLine(arr[N - 1]); } // Driver Code public static void Main(String[] args) { int []arr = { 2, 4, 6, 8, 0, 8 }; int N = arr.Length; findLastElement(arr, N); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for the above approach // Function to find the last remaining // array element after repeatedly removing // the smallest from pairs having absolute // difference 2 or 0 function findLastElement(arr, N) { // Sort the given array in // ascending order arr.sort(); let i = 0; // Traverse the array for (i = 1; i < N; i++) { // If difference between // adjacent elements is // not equal to 0 or 2 if (arr[i] - arr[i - 1] != 0 && arr[i] - arr[i - 1] != 2) { document.write( "-1" + "<br>" ); return ; } } // If operations can be performed document.write(arr[N - 1] + "<br>" ); } // Driver Code let arr = [ 2, 4, 6, 8, 0, 8 ]; let N = arr.length; findLastElement(arr, N); // This code is contributed by Surbhi Tyagi. </script> |
8
Time Complexity: O(N*logN), as we are using a inbuilt sort function.
Auxiliary Space: O(1), as we are not using any extra space.