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

Saksham Gupta
Last Updated: May 13, 2022

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.

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.

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;
}

Input

4 
1 2 3 4

Output

-1

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.

Key Takeaways

We saw how we could solve the problem, ‘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. For more such interesting questions, move over to our industry-leading practice platform CodeStudio to practice top problems and many more. Till then, Happy Coding!

 

Was this article helpful ?
0 upvotes