Reduce Array by replacing pair with their difference - Coding

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

Output

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.

Reffered: https://www.geeksforgeeks.org

DSA

Related
Count Substrings with Frequencies Less than Maximum Digit
Generate an Array such that Average of triplet exist in given Array
FIFO Principle of Queue
Min Length String with All Substrings of Size N
Maximum Ways to Cross the field

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	11