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

Debarati Ghatak
Last Updated: May 13, 2022

Introduction

In this problem, we are given an array (containing all positive integers) and an integer N. Our task is to obtain the maximum product of an array after subtracting one from any element N times.

We will be discussing two approaches to solve the problem - Naive and Efficient ones. So let's get started by first understanding the problem statement and a few test cases.

 

Source: tenor

Problem Statement

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

Test Case

Let us take a few sample test cases to understand the question.

Test Case 1

Input: M = 4, arr[] = {1, 7, 2, 6}, N = 2

Output: 60

Explanation: 1 is subtracted from element 7 two times. The final array becomes {1,5,2,6}. So the final product is 1*5*2*6 = 60.

 

Test Case 2

Input:  M = 4, arr[] = {1, 7, 2, 6}, N = 4

Output: 40

Explanation: 1 is subtracted from 7 two times, resulting in the array {1,5,2,6}. Then 1 is subtracted from element 6 once. Then the array becomes {1,5,2,5}. Now 1 is subtracted from element 5 (there are two 5s in the array, consider anyone). The final array becomes {1,4,2,5}. So the final product is 1*4*2*5 =  40.

 

Test Case 3

Input: M = 3, arr[] = {1,1,1} N = 1

Output: 0

Explanation: 1 is deleted from the first element. The array becomes {0,1,1,}. So the final product is 0*1*1 = 0.

Let us see how to solve the question:

Naive Approach

To obtain the maximum product, we need to subtract one from the current largest element from the given array N times. Subtracting one from any other element other than the current largest element will not give us the maximum product. 

We will now discuss the brute force approach that can be used to implement the idea. For the brute force approach, we need to sort the array in increasing order and subtract one from the last element of the array N times. 

After these operations have been done, the final product is calculated using the modified array.

Steps of algorithm

Perform the below steps N times

  • Sort array in increasing order
  • Subtract one from the largest element
  • Calculate the final product
  • Run a loop from 1 to M 
    • ans  = ans * arr[i]
  • Display ans

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
int solve(int M, int N, int arr[])
{
   int ans = 1;
   //performing below steps for N times
   for (int i = 0; i < N; i++)
   {
       //sort array in increasing order
       sort(arr, arr + M);
       //subtracting 1 from the largest element
       arr[M - 1] = arr[M - 1] - 1;
   }
   //calculating the final product
   for (int i = 0; i < M; i++)
       ans = ans * arr[i];
   cout << ans << endl;
}
int main()
{
   int M = 4, N = 2;
   int arr[5] = {1, 7, 2, 6};
   solve(M, N, arr);
}

 

Output:

 

Complexity Analysis

Time Complexity: O(N*(MlogM))

MlogM time is needed to sort the array of size M, and this sorting is performed N times. 

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

Space Complexity:  O(1)

No extra space is required in this approach.

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

 

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

Q1. 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.

 

Q2. What is the priority queue STL in CPP?

Ans: 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;

 

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

Ans: 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. 

 

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

Ans. 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.

Key Takeaways

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 CodeStudio to solve more problems for practice!

Happy coding, Ninja!

Was this article helpful ?
0 upvotes