Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Operation
2.2.
Example
2.2.1.
Explanation
3.
Approach 1 - Brute Force
3.1.
Program
3.2.
Complexity Analysis
4.
Approach 2 - Sorting
4.1.
Program
4.2.
Complexity Analysis
5.
Approach 3 - Max Heap
5.1.
Program
5.2.
Complexity Analysis
6.
Frequently Asked Questions
6.1.
What is a Priority Queue?
6.2.
How do we declare min heap in c++?
6.3.
Write applications of Priority Queue.
7.
Conclusion
Last Updated: Mar 27, 2024

Reduce the Array to at Most one Element by the Given Operation

Introduction

No one can value your time more than you. Thus you should always be aware of your priorities. If you can't do that, I recommend keeping a max heap for priority because you'll always get the essential task in O(1) time when you peep the top element from the heap. When the operating system schedules process tasks into the CPU, this is what it uses. Isn't it lovely how data structures can be linked to real-life scenarios? I do that all the time, and it helps me understand things better. 

To read more about max and min heap, refer to this lovely blog.

Today, we'll talk about a fascinating problem that can be solved with the max heap. So let's get started.

Also Read, Prefix Sum Array

Problem Statement

You are given an integer array of size 'N'. You have to perform a given operation on the array until its size reduces to one or zero.

Operation

  1. Extract the first two maximum elements from the array.
  2. If the difference between them is not zero, then insert their absolute difference (abs(MAX 1- MAX2)) into the array.

Example

‘ARR’ = [1, 8, 9, 4, 12, 5]

Output = 1

Explanation

  • Pop 12 and 9, and as their difference is not zero push abs(12 - 9) = 3, into the array. ‘ARR’ = [1, 8, 4, 5, 3].
  • Pop 8 and 5, and insert 3. ‘ARR’ = [1, 4, 3, 3].
  • Pop 4 and 3, and insert 1. ‘ARR’ = [1, 1, 3].
  • Pop 3 and 1, and insert 2. ‘ARR’ = [1, 2].
  • Pop 2 and 1, and insert 1. ‘ARR’ = [1].

Now ‘ARR.size()’ = 1, so return ‘ARR[0]’.

Approach 1 - Brute Force

In the brute force approach, we will find the maximum two elements from the array ‘ARR’ in linear time until we are left with only one element. Once we have the max elements, we’ll remove them and insert their difference into the array.

Let’s see how the algorithm will work. 

  • Loop through the array until its size is greater than 1.
  • In the loop, find the two maximum elements by looping through the array and then remove them and insert their difference into the array if it’s not zero.

Program

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

// Function to reduce the array to at most one element by given operation.
int reduceArray(vector<int> &arr)
{
   // Loop until the size of the array is greater than 1.
   while (arr.size() > 1)
   {
       // Initialize variables to store the two largest elements and their indices.
       int max1 = INT_MIN, max2 = INT_MIN, index1, index2;
       
       // Compute the two maximum elements.
       for (int i = 0; i < arr.size(); i++)
       {
           if (arr[i] > max1)
           {
               max2 = max1;
               max1 = arr[i];
               index2 = index1;
               index1 = i;
           }
           else if (arr[i] > max2)
           {
               max2 = arr[i];
               index2 = i;
           }
       }
       
       // Calculate the difference.
       int diff = abs(max1 - max2);
       
       // Update 'INDEX1' and 'INDEX2' such that 'INDEX1 > INDEX2'.
       if (index1 < index2)
       {
           int temp = index1;
           index1 = index2;
           index2 = temp;
       }
       
       // Remove the two maximum elements.
       arr.erase(arr.begin() + index1);
       arr.erase(arr.begin() + index2);
       
       // Insert the 'DIFF' if it's not zero.
       if (diff != 0)
           arr.push_back(diff);
   }
   
   return arr[0];
}
int main()
{
   int n;
   cout << "Enter the number of element in the array: ";
   cin >> n;
   vector<int> arr(n);
   cout << "Enter the array elements: ";
   for (int i = 0; i < n; i++)
   {
       cin >> arr[i];
   }
   
   int ans = reduceArray(arr);
   cout << "The remaining element in the array is:  " << ans << endl;
   
   return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Input

Enter the number of elements in the array: 7
Enter the array elements: 12 9 14 8 1 5 3

Output

The remaining element in the array is: 1

Complexity Analysis

Time Complexity

O(N ^ 2), where ‘N’ is the size of the array ‘ARR’.

We are computing the maximum two elements by looping through the whole array. This takes O(N) time, and we remove these elements from the array, which again takes O(N) time, and we are doing this ‘N’ + ‘N’/2 times. So the time complexity = O(3N/2 * (N + N)) = O(N ^ 2)

Space Complexity

O(1).

Since we are only using a couple of variables the space complexity is constant.

Approach 2 - Sorting

The first thing to notice is that we have to continuously pop the maximum element from the array. Hence by sorting the array, we can do this in O(1) time. Now that we've figured out how to pop max elements let's think about how we are going to insert abs(MAX1 - MAX2) into the array. Since our array is sorted, we can find the position of the new element in O(log(N)) time using binary search and insert it in the correct place. 

Let’s see how the algorithm works.

  • Firstly, Sort the array, ‘ARR’.
  • Now loop through the array until its size is greater than 1.
  • Inside the loop, pop the last two elements of the array and compare them. If they are not equal, insert their absolute difference inside the array using another insertInArray() function, which uses binary search to find the appropriate position for insertion.
  •  In the end, if array size is 1 return ARR[0] else return 0.

Program

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

// Function to insert ‘VAL’ into sorted array, ‘ARR’ at its correct position.
void insertInArray(vector<int> &arr, int val)
{
   // Initialize left and right bound.
   int l = 0, r = arr.size() - 1, mid;
   
   // Loop until the ‘LEFT’ is smaller than ‘RIGHT’.
   while (l < r)
   {
       mid = (l + r) / 2;
       
       // If the ‘MID’ value is equal to ‘VAL’ then break as we've found the correct position.
       if (arr[mid] == val)
           break;
           
       // If the ‘MID’ value is greater than ‘VAL’, update R.
       else if (arr[mid] > val)
           r = mid - 1;
           
       // Else update L.
       else
           l = mid + 1;
   }
   
   // Insert ‘VAL’ at its correct position.
   arr.insert(arr.begin() + mid, val);
}

// Function to reduce the array to at most one element by given operation.
int reduceArray(vector<int> &arr)
{
   // Sort the array.
   sort(arr.begin(), arr.end());
   
   // Loop until array size is greater than 1.
   while (arr.size() > 1)
   {
       // Pop the last two elements of the array.
       int max1 = arr[arr.size() - 1];
       arr.pop_back();
       int max2 = arr[arr.size() - 1];
       arr.pop_back();
       
       // If the maximum two elements are not equal, push their absolute. Hence the difference in the array.
       if (max1 != max2)
       {
           insertInArray(arr, abs(max1 - max2));
       }
   }
   
   if (arr.size() == 1)
       return arr[0];
   return 0;
}

int main()
{
   int n;
   cout << "Enter the number of element in the array: ";
   cin >> n;
   vector<int> arr(n);
   cout << "Enter the array elements: ";
   for (int i = 0; i < n; i++)
   {
       cin >> arr[i];
   }
   
   int ans = reduceArray(arr);
   cout << "The remaining element in the array is:  " << ans << endl;
   
   return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Input

Enter the number of elements in the array: 10
Enter the array elements: 7 8 13 3 4 8 1 15 16 20

Output

The remaining element in the array is: 1

Complexity Analysis

Time Complexity

O(N^2), where ‘N’ is the size of the array

We sort an array of size 'N' takes O(N*log N).

And from the while loop, in total, we insert 'N - 1’ elements into the array, and inserting an element at any position takes O(M), where  'M' is the number of elements moved. 

Hence time complexity is O((N - 1) * M) which is roughly O(N ^ 2).

Space Complexity

O(1).

Since we are only using a couple of variables.

Approach 3 - Max Heap

In this approach, we'll be using a Max Heap since extraction of max elements can be done in O(log N) time, and insertion takes O(log N) time. We'll be using the STL priority queue for creating the max heap. What we'll do basically is insert all array elements into the priority queue and then loop through the priority queue until its size is greater than one. With every iteration, pop the first two top elements from the priority queue, and compare if their difference. If not zero, then insert their absolute difference into the priority queue.

However, even if the implementation of this approach is pretty simple, let's take a look at the algorithm.

  • Initialize a max heap priority queue, PQ.
  • Insert all array elements into PQ.
  • Now loop until PQ.size() > 1 and extract max two elements from the priority queue.
  • If they are not equal, insert their absolute difference into PQ.
  • Last, return PQ.top() if PQ.size() == 1 else return 0.

Program

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Function to reduce the array to at most one element by given operation.
int reduceArray(vector<int> &arr)
{
   // For max heap, we declare a priority queue.
   priority_queue<int> pq;
   // Insert all array elements in the priority queue.
   for (int &element: arr)
   {
       pq.push(element);
   }
   // Loop until the size of the priority queue is greater than 1.
   while (pq.size() > 1)
   {
       // Pop the top two elements of ‘PQ’, which will give us max two elements.
       int max1 = pq.top();
       pq.pop();
       int max2 = pq.top();
       pq.pop();
       // If the difference between the two max elements is non-zero, then push their absolute difference into ‘PQ’.
       if (max1 != max2)
       {
           pq.push(abs(max1 - max2));
       }
   }
   // If ‘PQ’ is not empty, return the top element.
   if (pq.size() == 1)
       return pq.top();
   // Else return 0.
   return 0;
}
int main()
{
   int n;
   cout << "Enter the number of element in the array: ";
   cin >> n;
   vector<int> arr(n);
   cout << "Enter the array elements: ";
   for (int i = 0; i < n; i++)
   {
       cin >> arr[i];
   }
   int ans = reduceArray(arr);
   cout << "The remaining element in the array is: " << ans << endl;
   return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Input

Enter the number of elements in the array: 12
Enter the array elements: 12 18 34 21 56 12 6 29 43 49 18 26

Output

The remaining element in the array is: 2

Complexity Analysis

Time Complexity

O(N * (log(N)), where 'N' is the size of the array.

We are inserting ‘N’ elements in the priority queue and each insertion takes O(log N) time, hence the time complexity for insertion is O(N log N).

And from the while loop, in total, we are again inserting N - 1 element into the priority queue, resulting in additional (N - 1) * log(N) time complexity.

Hence, Overall Time Complexity = O(N * log N) + O((N - 1) * log N) = O(N * log N).

Space Complexity

O(N), where 'N' is the size of the array.

Since we are using a priority queue of size 'N’.

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 

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

Heap is an important data structure for coding interviews. If you're looking for an SDE job, you should solve more heap problems. I hope you found this blog interesting. Visit Coding Ninjas Studio Library to read more amazing blogs like this.

Recently Coding Ninjas has also released a specially designed test series for acing Interviews- Coding Ninjas Studio Test Series.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

A linked list is a linear data structure that consists of nodes. Each Node contains a data field and a pointer to the next Node. In Linked List, unlike arrays, elements are not stored at contiguous memory locations but rather at different memory locations. Linked Lists are one of the most fundamental and important data structures having a wide range of applications. Linked Lists are also important from the perspective of interviews as well. 

Thanks for reading.

Live masterclass