Maximum product of an Array after subtracting 1 from any element N times
Given an array arr[] of positive integers of size M and an integer N, the task is to maximize the product of array after subtracting 1 from any element N number of times
Examples:
Input: M = 5, arr[] = {5, 1, 7, 8, 3}, N = 2
Output: 630
Explanation: After subtracting 1 from arr[3] 2 times, array becomes {5, 1, 7, 6, 3} with product = 630
Input: M = 2, arr[] = {2, 2}, N = 4
Output: 0
Explanation: After subtracting 2 from arr[0] and arr[1] 2 times each, array becomes {0, 0} with product = 0
Approach: The task can be solved with the help of max-heap Follow the below steps to solve the problem:
- Insert all the elements inside a max-heap
- Pop the top element from the max- heap, and decrement 1 from it, also decrement N
- Insert the popped element back to max-heap
- Continue this process till N > 0
- The maximum product will be the product of all the elements inside the max-heap
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum // product of the array int getMax( int m, int arr[], int n) { // Max-heap priority_queue< int > q; // Store all the elements inside max-heap for ( int i = 0; i < m; i++) q.push(arr[i]); // n operations while (n--) { int x = q.top(); q.pop(); // Decrement x --x; // Push back x inside the heap q.push(x); } // Store the max product possible int ans = 1; while (!q.empty()) { ans *= q.top(); q.pop(); } return ans; } // Driver Code int main() { int M = 5; int arr[5] = { 5, 1, 7, 8, 3 }; int N = 2; cout << getMax(M, arr, N); } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find the maximum // product of the array static Integer getMax( int m, Integer arr[], int n) { // Max-heap PriorityQueue<Integer> q = new PriorityQueue<Integer>( Collections.reverseOrder()); // Store all the elements inside max-heap for ( int i = 0 ; i < m; i++) q.add(arr[i]); // n operations while (n-- != 0 ) { Integer x = q.poll(); // Decrement x --x; // Push back x inside the heap q.add(x); } // Store the max product possible Integer ans = 1 ; while (q.size() != 0 ) { ans *= q.poll(); } return ans; } // Driver Code public static void main(String[] args) { int M = 5 ; Integer arr[] = { 5 , 1 , 7 , 8 , 3 }; int N = 2 ; System.out.println(getMax(M, arr, N)); } } // This code is contributed by Potta Lokesh |
Python3
# python program for the above approach from queue import PriorityQueue # Function to find the maximum # product of the array def getMax(m, arr, n): # Max-heap q = PriorityQueue() # Store all the elements inside max-heap for i in range ( 0 , m): q.put( - arr[i]) # n operations while (n): n - = 1 x = - q.get() # Decrement x x - = 1 # Push back x inside the heap q.put( - x) # Store the max product possible ans = 1 while ( not q.empty()): ans * = - q.get() return ans # Driver Code if __name__ = = "__main__" : M = 5 arr = [ 5 , 1 , 7 , 8 , 3 ] N = 2 print (getMax(M, arr, N)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to find the maximum // product of the array static int getMax( int m, int []arr, int n) { // Max-heap List< int > q = new List< int >(); // Store all the elements inside max-heap for ( int i = 0; i < m; i++){ q.Add(arr[i]); } q.Sort(); q.Reverse(); // n operations while (n-- != 0) { int x = q[0]; q.RemoveAt(0); // Decrement x --x; // Push back x inside the heap q.Add(x); q.Sort(); q.Reverse(); } // Store the max product possible int ans = 1; while (q.Count != 0) { ans *= q[0]; q.RemoveAt(0); } return ans; } // Driver Code public static void Main(String[] args) { int M = 5; int []arr = { 5, 1, 7, 8, 3 }; int N = 2; Console.WriteLine(getMax(M, arr, N)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program for the above approach // Function to find the maximum // product of the array function getMax(m, arr, n) { // Max-heap let q = []; // Store all the elements inside max-heap for (let i = 0; i < m; i++) { q.push(arr[i]); } q.sort(); q.reverse(); // n operations while (n-- != 0) { let x = q[0]; q.splice(0, 1); // Decrement x --x; // Push back x inside the heap q.push(x); q.sort(); q.reverse(); } // Store the max product possible let ans = 1; while (q.length != 0) { ans *= q[0]; q.splice(0, 1); } return ans; } // Driver Code let M = 5; let arr = [5, 1, 7, 8, 3]; let N = 2; document.write(getMax(M, arr, N)); // This code is contributed by gfgking </script> |
Output
630
Time Complexity: O(nlogm)
Auxiliary Space: O(m)
Contact Us