Given an array arr[] of N elements, the task is to perform the following operation:
- Pick the two largest element from the array and remove these element. If the elements are unequal then insert the absolute difference of the elements into the array.
- Perform the above operations until array has 1 or no element in it. If the array has only one element left then print that element, else print “-1”.
Examples:
Input: arr[] = { 3, 5, 2, 7 }
Output: 1
Explanation:
The two largest elements are 7 and 5. Discard them. Since both are not equal, insert 7 – 5 = 2 into the array. Hence, arr[] = { 3, 2, 2 }
The two largest elements are 3 and 2. Discard them. Since both are not equal, insert 3 – 2 = 1 into the array. Hence, arr[] = { 1, 2 }
The two largest elements are 2 and 1. Discard them. Since both are not equal, insert 2 – 1 = 1 into the array. Hence, arr[] = { 1 }
The only element left is 1. Print the value of the only element left.Input: arr[] = { 3, 3 }
Output: -1
Explanation:
The two largest elements are 3 and 3. Discard them. Now the array has no elements. So, print -1.
Approach: To solve the above problem we will use Priority Queue Data Structure. Below are the steps:
- Insert all the array elements in the Priority Queue.
- As priority queue is based on the implementation of Max-Heap. Therefore removing element from it gives the maximum element.
- Till the size of priority queue is not less than 2, remove two elements(say X & Y) from it and do the following:
- If X and Y are not same then insert the absolute value of X and Y into the priority queue.
- Else return to step 3.
- If the heap has only one element then print that element.
- Else print “-1”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print the remaining elementint final_element(int arr[], int n){ // Priority queue can be used // to construct max-heap priority_queue<int> heap; // Insert all element of arr[] // into priority queue for (int i = 0; i < n; i++) heap.push(arr[i]); // Perform operation until heap // size becomes 0 or 1 while (heap.size() > 1) { // Remove largest element int X = heap.top(); heap.pop(); // Remove 2nd largest element int Y = heap.top(); heap.pop(); // If extracted element // are not equal if (X != Y) { // Find X - Y and push // it to heap int diff = abs(X - Y); heap.push(diff); } } // If heap size is 1, then // print the remaining element if (heap.size() == 1) { cout << heap.top(); } // Else print "-1" else { cout << "-1"; }}// Driver Codeint main(){ // Given array arr[] int arr[] = { 3, 5, 2, 7 }; // Size of array arr[] int n = sizeof(arr) / sizeof(arr[0]); // Function Call final_element(arr, n); return 0;} |
Java
// Java program for the above approach import java.io.*; import java.util.Collections;import java.util.*;class GFG{ // Function to print the remaining element static public int final_element(Integer[] arr, int n){ if(arr == null) { return 0; } // Priority queue can be used // to construct max-heap PriorityQueue<Integer> heap = new PriorityQueue<Integer>(Collections.reverseOrder()); // Insert all element of arr[] // into priority queue for(int i = 0; i < n; i++) { heap.offer(arr[i]); } // Perform operation until heap // size becomes 0 or 1 while (heap.size() > 1) { // Remove largest element int X = heap.poll(); // Remove 2nd largest element int Y = heap.poll(); // If extracted element // are not equal if (X != Y) { // Find X - Y and push // it to heap int diff = Math.abs(X - Y); heap.offer(diff); } } // If heap size is 1, then // print the remaining element // Else print "-1" return heap.size() == 1 ? heap.poll() : -1;}// Driver codepublic static void main (String[] args) { // Given array arr[] Integer arr[] = new Integer[] { 3, 5, 2, 7}; // Size of array arr[] int n = arr.length; // Function Call System.out.println(final_element(arr, n)); }}// This code is contributed by deepika_sharma |
Python3
# Python3 program for the above approach from queue import PriorityQueue# Function to print the remaining elementdef final_element(arr, n): # Priority queue can be used # to construct max-heap heap = PriorityQueue() # Insert all element of # arr[] into priority queue. # Default priority queue in Python # is min-heap so use -1*arr[i] for i in range(n): heap.put(-1 * arr[i]) # Perform operation until heap # size becomes 0 or 1 while (heap.qsize() > 1): # Remove largest element X = -1 * heap.get() # Remove 2nd largest element Y = -1 * heap.get() # If extracted elements # are not equal if (X != Y): # Find X - Y and push # it to heap diff = abs(X - Y) heap.put(-1 * diff) # If heap size is 1, then # print the remaining element if (heap.qsize() == 1): print(-1 * heap.get()) # Else print "-1" else: print("-1")# Driver Codeif __name__ == '__main__': # Given array arr[] arr = [ 3, 5, 2, 7 ] # Size of array arr[] n = len(arr) # Function call final_element(arr, n)# This code is contributed by himanshu77 |
C#
// C# program for the above approach using System;using System.Collections.Generic;class GFG{ // Function to print the remaining element static void final_element(int[] arr, int n) { // Priority queue can be used // to construct max-heap List<int> heap = new List<int>(); // Insert all element of arr[] // into priority queue for(int i = 0; i < n; i++) heap.Add(arr[i]); // Perform operation until heap // size becomes 0 or 1 while (heap.Count > 1) { // Remove largest element heap.Sort(); heap.Reverse(); int X = heap[0]; heap.RemoveAt(0); // Remove 2nd largest element int Y = heap[0]; heap.RemoveAt(0); // If extracted element // are not equal if (X != Y) { // Find X - Y and push // it to heap int diff = Math.Abs(X - Y); heap.Add(diff); } } // If heap size is 1, then // print the remaining element if (heap.Count == 1) { heap.Sort(); heap.Reverse(); Console.Write(heap[0]); } // Else print "-1" else { Console.Write(-1); } } // Driver codestatic void Main() { // Given array arr[] int[] arr = { 3, 5, 2, 7 }; // Size of array arr[] int n = arr.Length; // Function Call final_element(arr, n);}}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// Javascript program for the above approach// Function to print the remaining elementfunction final_element(arr, n){ // Priority queue can be used // to construct max-heap var heap = []; // Insert all element of arr[] // into priority queue for (var i = 0; i < n; i++) heap.push(arr[i]); heap.sort((a,b)=>a-b); // Perform operation until heap // size becomes 0 or 1 while (heap.length > 1) { // Remove largest element var X = heap[heap.length-1]; heap.pop(); // Remove 2nd largest element var Y = heap[heap.length-1]; heap.pop(); // If extracted element // are not equal if (X != Y) { // Find X - Y and push // it to heap var diff = Math.abs(X - Y); heap.push(diff); } heap.sort((a,b)=>a-b); } // If heap size is 1, then // print the remaining element if (heap.length == 1) { document.write(heap[heap.length-1]); } // Else print "-1" else { document.write("-1"); }}// Driver Code// Given array arr[]var arr = [3, 5, 2, 7 ];// Size of array arr[]var n = arr.length;// Function Callfinal_element(arr, n);// This code is contributed by rutvik_56.</script> |
Output:
1
Time Complexity: O(N*log(N))
Auxiliary Space Complexity: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!