Table of contents
1.
Introduction
2.
Understanding the Problem
3.
Intuition
3.1.
Code
3.2.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a Priority Queue?
4.2.
How do we declare min heap in c++?
4.3.
Write applications of Priority Queue.
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Last Element Remaining by Deleting the Two Largest Elements and Replacing them with Their Absolute Difference If They are Unequal

Author Saksham Gupta
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Interviews after Interviews,, we see questions related to priority queue being asked. So having a good grip over the priority queue surely gives us an upper hand over the rest of the competition. But you don’t need to worry about any of it because Ninjas are here with you. Today we will see one such question named ‘Last element remaining by deleting the two largest elements and replacing them with their absolute difference if they are unequal’. Now let’s see the problem statement in detail.

Also see, Data Structures

Understanding the Problem

We have been given an array, and our task is to pick the two largest elements in the array and remove them. Now, if these elements are unequal, we will insert the absolute difference of the elements into the array. We will keep performing this until the array has 1 or no elements left in it. If there is only one element left in the array, then we will print that. Otherwise, we will print ‘-1’.

Let’s understand the problem better by the following example.

ARR = {1, 2, 3, 4}

Explanation

Let’s understand this step by step:

  • Initially, 3 and 4 are the two largest elements in the array, so we will take them out, and also, as they are not equal, we will insert their absolute difference (4 - 3) in the array. So now array becomes {1, 2, 1}
  • Now, 1, 2 are the two largest elements. They are not equal. Thus, we will insert their absolute difference (2 - 1) in the array. So now the array becomes {1, 1}.
  • Now, 1, 1 are the two largest elements of the array. Now, both of them are equal. Thus, we did not insert anything in the array.
  • Now the size of the array becomes 0. Thus, we will print -1.
    Also Read, Prefix Sum Array

Intuition

As we have to regularly maintain the sorted array and have to pick the top two largest elements from it. The direction in which our mind first goes is towards the Priority queue. The idea here is to use a max priority queue. We will first insert all the elements in the priority queue. Then we will keep performing the following operations till the size of the queue becomes 1 or 0:

  • Take two elements at the top of the queue. Pop them.
  • If they are not equal, then we will insert their absolute difference. Else, we will continue.

Now, if the size of the queue is 0, we will print ‘-1’. Else if its size is one, then we will print that single element present in the queue.

Things will become much clearer from the code.

Code

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// Function to reduce the array and print the remaining element.
int reduceArray(vector<int> &arr)
{
   priority_queue<int> maxPq;

   // Inserting elements of array in priority_queue.
   for (int i = 0; i < arr.size(); i++)
       maxPq.push(arr[i]);

   // Looping through elements.
   while (maxPq.size() > 1)
   {
       // Remove largest element.
       int maxEle = maxPq.top();
       maxPq.pop();

       // Remove 2nd largest element.
       int secondMaxEle = maxPq.top();
       maxPq.pop();

       // If these are not equal.
       if (maxEle != secondMaxEle)
       {
           // Pushing into queue.
           maxPq.push((maxEle - secondMaxEle));
       }
   }

   // If only one element is there in the heap.
   if (maxPq.size() == 1)
       cout << maxPq.top();
   else
       cout << "-1";
}

int main()
{
   // Taking user input.
   int n;
   cin >> n;
   vector<int> arr(n, 0);
   for (int i = 0; i < n; i++)
       cin >> arr[i];

   // Calling function 'reduceArray()'.
   reduceArray(arr);
   return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Input

4 
1 2 3 4

Output

-1

Complexity Analysis

Time Complexity

O(N * log N), where ‘N’ is the length of the array.

As we are inserting ‘N’ elements in the priority queue and each insertion costs us O(log N) time thus ‘N’ insertions will cost O(N * log N). After insertion we are just looping through all the elements in the queue that will cost us O(N) time. Thus the overall complexity is O(N) + O(N * log N) ~ O(N * log N).

Space Complexity

O(N), where ‘N’ is the length of the array.

As we are using a priority queue to store the elements in the queue and as there are ‘N’ elements, extra space of O(N) will be required.

Frequently Asked Questions

What is a Priority Queue?

This is the implementation of the heap in which the root element is a higher priority in the form of maximum or minimum.

How do we declare min heap in c++?

priority_queue< data_type, vector<data_type>, greater<data_type>> variable_name 
You can also try this code with Online C++ Compiler
Run Code

Write applications of Priority Queue.

Application of priority queue are as follows:-

   1. Some algorithms like Dijkstra’s shortest path algorithm, Prim’s Minimum Spanning Tree, etc

   2. CPU scheduling in the operating system.

   3. Sorting algorithm like heap-sort.

Conclusion

We saw how we could solve the problem, ‘the last element remaining by deleting the two largest elements and replacing them with their absolute difference if they are unequal’ with the help of a priority queue. We first inserted all the elements in the queue and then, according to the question popped the top two elements. 

Recommended Reading:

For more such interesting questions, move over to our industry-leading practice platform Coding Ninjas Studio to practice top problems and many more. 

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Till then, Happy Coding!

 

Live masterclass