Reduce Array by replacing pair with their difference
You are given an array of positive integers. You can perform the following operations on the array any number of times:
- Select the two largest elements in the array, suppose a and b.
- If a = b, remove both of them from the array.
- If a > b, remove b and the new value of a will be a-b or vice-versa.
This process continues until there is either one element left or all the elements have been removed. You have to find the last element remaining or return 0 if there is none.
Examples:
Input: [1, 2, 3, 6, 7, 7]
Output: 0
Explanation: We start with two largest elements. In this case, they are two equal elements with value 7, so they both are removed. Then, the next elements are 3 and 6. Discard the smaller one and the larger one will now be of length 6-3 = 3. Then, the next elements are of 3 and 2. Again the smaller will be discarded and larger one will now be 3-2 = 1. Now there are two equal elements, 1, hence both will be discarded and output will be 0.Input: [2, 4, 5]
Output: 1
Explanation: In this case, the two largest elements are 4 and 5. As 4 is smaller it will be discarded and the larger will become 5-4 = 1. Now there are only two elements remaining which are 1 and 2. Hence 1 will be discarded and the final output will be 2-1 = 1.
Approach:
As the problem has to repeatedly find the two largest items from a given array, we can think of a priority queue (Max heap) in this case. Using a max heap, we can perform the required operations until the given condition is reached.
Follow the below steps to implement the above idea:
- Create a priority queue (max heap) named ‘pq’ to store the items in a decreasingly sorted manner.
- Traverse through the array and insert each item into the heap.
- Till there are atleast 2 items in the heap, perform the following operations as stated in the problem:
- Store the two largest elements from the max-heap in two different variables named as ‘a’ and ‘b’.
- If the values of ‘a’ and ‘b’ are not equal, reduce the length of ‘b’ from ‘a’.
- Push the updated value of ‘a’ into the max-heap and continue performing these steps.
- Once these above operations are performed, check if the size of pq is 1.
- If it is equal to 1, that means one element is remaining which cannot be integrated further. So return the element as our answer.
- If it is not 1, then all the elements have been removed and none is remaining. So we return 0 as our answer.
Implementation of the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the last element remaining int lastElement(vector< int >& arr) { int n = arr.size(); // Create a max heap priority_queue< int > pq; // Push all the elements into the heap for ( int i = 0; i < n; i++) { pq.push(arr[i]); } // Perform the operations till the size of heap is // greater than 1 while (pq.size() > 1) { // Pop the top two elements int a = pq.top(); pq.pop(); int b = pq.top(); pq.pop(); // If both the elements are not equal if (a != b) { // Reduce the length of the larger element a -= b; // Push the updated value into the heap pq.push(a); } } // If one element is left return its value if (pq.size() == 1) { return pq.top(); } // If no element is left return 0 return 0; } // Driver Code int main() { // Input vector vector< int > arr = { 2, 4, 5 }; // Function call cout << lastElement(arr) << endl; return 0; } |
Java
// Java Code for the above approach import java.util.*; public class GFG { // Function to find the last element remaining public static int lastElement( int [] arr) { int n = arr.length; // Create a max heap PriorityQueue<Integer> pq = new PriorityQueue<>( (a, b) -> Integer.compare(b, a)); // Push all the elements into the heap for ( int i = 0 ; i < n; i++) { pq.add(arr[i]); } // Perform the operations until the size of the heap // is greater than 1 while (pq.size() > 1 ) { // Pop the top two elements int a = pq.poll(); int b = pq.poll(); // If both the elements are not equal if (a != b) { // Reduce the length of the larger element a -= b; // Push the updated value into the heap pq.add(a); } } // If one element is left, return its value if (pq.size() == 1 ) { return pq.peek(); } // If no element is left, return 0 return 0 ; } // Driver Code public static void main(String[] args) { // Input array int [] arr = { 1 , 2 , 3 , 6 , 7 , 7 }; // Function call System.out.println(lastElement(arr)); } } |
Python3
import heapq # Function to find the last element remaining def last_element(arr): n = len (arr) # Create a max heap pq = [ - x for x in arr] heapq.heapify(pq) # Perform the operations till the size of heap is # greater than 1 while len (pq) > 1 : # Pop the top two elements a = - heapq.heappop(pq) b = - heapq.heappop(pq) # If both the elements are not equal if a ! = b: # Reduce the length of the larger element a - = b # Push the updated value into the heap heapq.heappush(pq, - a) # If one element is left return its value if len (pq) = = 1 : return - pq[ 0 ] # If no element is left return 0 return 0 # Driver Code if __name__ = = "__main__" : # Input list arr = [ 2 , 4 , 5 ] # Function call print (last_element(arr)) |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to find the last element remaining static int LastElement(List< int > arr) { int n = arr.Count; // Create a max heap var pq = new PriorityQueue< int >(); // Push all the elements into the heap for ( int i = 0; i < n; i++) { pq.Push(arr[i]); } // Perform the operations till the size of heap is // greater than 1 while (pq.Count > 1) { // Pop the top two elements int a = pq.Pop(); int b = pq.Pop(); // If both the elements are not equal if (a != b) { // Reduce the length of the larger element a -= b; // Push the updated value into the heap pq.Push(a); } } // If one element is left return its value if (pq.Count == 1) { return pq.Top(); } // If no element is left return 0 return 0; } // Driver Code static void Main() { // Input list List< int > arr = new List< int >{ 2, 4, 5 }; // Function call Console.WriteLine(LastElement(arr)); } } // Priority Queue Implementation public class PriorityQueue<T> where T : IComparable<T> { private List<T> heap; public PriorityQueue() { heap = new List<T>(); } public int Count { get { return heap.Count; } } public void Push(T value) { heap.Add(value); int currentIndex = heap.Count - 1; while (currentIndex > 0) { int parentIndex = (currentIndex - 1) / 2; if (heap[currentIndex].CompareTo( heap[parentIndex]) > 0) { Swap(currentIndex, parentIndex); currentIndex = parentIndex; } else { break ; } } } public T Pop() { if (Count == 0) { throw new InvalidOperationException( "Priority queue is empty" ); } T root = heap[0]; heap[0] = heap[Count - 1]; heap.RemoveAt(Count - 1); int currentIndex = 0; while ( true ) { int leftChildIndex = currentIndex * 2 + 1; int rightChildIndex = currentIndex * 2 + 2; if (leftChildIndex >= Count) { break ; } int childIndex = leftChildIndex; if (rightChildIndex < Count && heap[rightChildIndex].CompareTo( heap[leftChildIndex]) > 0) { childIndex = rightChildIndex; } if (heap[currentIndex].CompareTo( heap[childIndex]) < 0) { Swap(currentIndex, childIndex); currentIndex = childIndex; } else { break ; } } return root; } public T Top() { if (Count == 0) { throw new InvalidOperationException( "Priority queue is empty" ); } return heap[0]; } private void Swap( int index1, int index2) { T temp = heap[index1]; heap[index1] = heap[index2]; heap[index2] = temp; } } // This code is contributed by Susobhan Akhuli |
Javascript
// Javascript program for the above approach // Function to find the last element remaining function lastElement(arr) { const n = arr.length; // Create a max heap const pq = new MaxHeap(); // Push all the elements into the heap for (let i = 0; i < n; i++) { pq.push(arr[i]); } // Perform the operations until the size of heap is greater than 1 while (pq.size() > 1) { // Pop the top two elements const a = pq.pop(); const b = pq.pop(); // If both the elements are not equal if (a !== b) { // Reduce the length of the larger element const diff = a - b; // Push the updated value into the heap pq.push(diff); } } // If one element is left return its value if (pq.size() === 1) { return pq.pop(); } // If no element is left return 0 return 0; } // MaxHeap class to simulate max heap functionality class MaxHeap { constructor() { this .heap = []; } push(value) { this .heap.push(value); this .heapifyUp(); } pop() { if ( this .isEmpty()) { return null ; } if ( this .heap.length === 1) { return this .heap.pop(); } const root = this .heap[0]; this .heap[0] = this .heap.pop(); this .heapifyDown(); return root; } size() { return this .heap.length; } isEmpty() { return this .size() === 0; } heapifyUp() { let index = this .size() - 1; while (index > 0) { const parentIndex = Math.floor((index - 1) / 2); if ( this .heap[index] > this .heap[parentIndex]) { this .swap(index, parentIndex); index = parentIndex; } else { break ; } } } heapifyDown() { let index = 0; const length = this .size(); while ( true ) { const leftChildIndex = 2 * index + 1; const rightChildIndex = 2 * index + 2; let largest = index; if ( leftChildIndex < length && this .heap[leftChildIndex] > this .heap[largest] ) { largest = leftChildIndex; } if ( rightChildIndex < length && this .heap[rightChildIndex] > this .heap[largest] ) { largest = rightChildIndex; } if (largest !== index) { this .swap(index, largest); index = largest; } else { break ; } } } swap(i, j) { [ this .heap[i], this .heap[j]] = [ this .heap[j], this .heap[i]]; } } // Driver Code const arr = [2, 4, 5]; // Function call console.log(lastElement(arr)); // This code is contributed by Susobhan Akhuli |
1
Time Complexity: O(N*log(N)). The all insertions in a priority queue takes O(N*log(N)) time and the time for each pop and top operation takes O(log(N)) time.
Auxiliary space: O(N),as we have used an extra space of a priority queue data structure.