Maximum product of an Array after subtracting 1 from any element N times

Efficient Approach

We can reduce the time complexity of our previous approach using max heap data structure. To implement the same idea using max heap, we will have to first insert all the array elements in the max heap. 

In a max heap data structure, the top element refers to the largest element of the heap. So we will run a loop for N times, 

1. Pop the top element from heap
2. Decrease the top element by one
3. Push the decreased element into heap

After the above operations have been done N times, the final product will be calculated using the modified heap.

Steps of algorithm

• Push all elements of the given array in a max heap
• Perform the below steps N times
  • Pop the largest element/top from heap
  • Subtract one from the largest element/top
  • Push the element in heap after subtraction
• Calculate the final product
• Display the final product

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
int solve(int M, int N, int arr[])
{
   priority_queue<int> pq;
   int ans = 1;
   //pushing elements of array in max heap
   for (int i = 0; i < M; i++)
       pq.push(arr[i]);
   //performing below steps for N times
   for (int i = 0; i < N; i++)
   {
       int k = pq.top();
       //pop the largest element/top from heap
       pq.pop();
       //subtracting 1 from the largest element/top
       k = k - 1;
       //push the element after subtraction
       pq.push(k);
   }
   //calculating the final product
   while (!pq.empty())
   {
       ans = ans * pq.top();
       pq.pop();
   }
   cout << ans << endl;
}
int main()
{
   int M = 4, N= 2;
   int arr[5] = {1, 7, 2, 6};
   solve(M, N, arr);
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Complexity Analysis

Time Complexity: O(NlogM)

The time taken to push and pop elements from a heap takes logM time. The push and pop operations are performed N times, so the complexity becomes O(NlogM).

Here, N refers to the given integer, and M refers to the size of the array.

Space Complexity:  O(M)

The space required is O(M) as we are using a max heap of size M. Here, M refers to the size of the array.

Frequently Asked Questions

What is sort() STL in CPP?

Ans: The sort() STL sorts an array or vector in ascending order (by default). It takes two input parameters,

1. Beginning of the array
2. Length of the array up to which the sorting needs to be done

Example: sort(arr, arr + n);

Here, arr is an array that will be sorted from index 1 to n-1 in increasing order.

To sort the array in descending order, a third parameter should be passed. That third parameter is the greater function.

Example: sort(arr, arr + n, greater<int>());

Here, arr is an array that will be sorted from index 1 to n-1 in decreasing order.

What is the priority queue STL in CPP?

A priority queue is a type of container adapter present in the STL library of CPP, which allows constant lookup and logarithmic insertion and deletion. It is designed so that the first element is the largest in the queue. Priority queues are like normal queues, but every element has a ‘priority’ associated.

By default, it functions like a max-heap in CPP. 

Example: priority_queue<int> pq;

Using the above line, an empty priority queue of type ‘int’ and name ‘pq’ is created.

For creating a min-heap, the following syntax is used

priority_queue<int,vector<int>,greater<int>> pq;

What are the various methods of priority queue STL in CPP?

The various methods of priority queue STL in CPP are as follows,

• push() - To add an element.
• pop() - To delete the largest element in the container.
• top() - To return a reference to the topmost/largest element in the container.
• empty() - To check whether the container is empty or not.
• size() - To return the size of the container.
• swap() - To swap the contents of one priority queue with another priority queue that has the same type and size.
• emplace() - To add an element which is constructed in-place. 

What are the time complexities of the top(), push(), and pop() methods of priority queue STL in CPP?

The time complexities are:

• top() has O(1).
• push() has O(logn), where n refers to the number of elements in the priority queue.
• pop() has O(logn), where n refers to the number of elements in the priority queue.

Conclusion

To conclude this blog, we learned how to approach and solve this question “Maximum product of an Array after subtracting 1 from any element N times”. 

We solved the given question using a naive approach and an efficient one (using max heap). We hope you now have a better knowledge of the solution to this problem. Check out our amazing blog on heap data structure to learn more about heaps.

And don't forget to visit Coding Ninjas Studio to solve more problems for practice!

Recommended Readings:

• Top Array Coding Interview Questions
• Merge K Sorted Arrays
• Reduce the Array to at Most one Element by Performing Given Operations
• Kth Smallest Pair Sum in the Given Array
• Application of Priority Queue
• Applications of Heap Data Structure
• Practise Problems

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.

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.

Happy coding, Ninja!