Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2233.html

2233. Maximum Product After K Increments (Medium)

You are given an array of non-negative integers nums and an integer k. In one operation, you may choose any element from nums and increment it by 1.

Return the maximum product of nums after at most k operations. Since the answer may be very large, return it modulo 109 + 7. Note that you should maximize the product before taking the modulo. 

 

Example 1:

Input: nums = [0,4], k = 5
Output: 20
Explanation: Increment the first number 5 times.
Now nums = [5, 4], with a product of 5 * 4 = 20.
It can be shown that 20 is maximum product possible, so we return 20.
Note that there may be other ways to increment nums to have the maximum product.

Example 2:

Input: nums = [6,3,3,2], k = 2
Output: 216
Explanation: Increment the second number 1 time and increment the fourth number 1 time.
Now nums = [6, 4, 3, 3], with a product of 6 * 4 * 3 * 3 = 216.
It can be shown that 216 is maximum product possible, so we return 216.
Note that there may be other ways to increment nums to have the maximum product.

 

Constraints:

• 1 <= nums.length, k <= 105
• 0 <= nums[i] <= 106

Similar Questions:

• Minimum Size Subarray Sum (Medium)
• Minimum Increment to Make Array Unique (Medium)
• Minimum Operations to Make the Array Increasing (Easy)

Solution 1. Heap

• C++
• Python
• Java
• Go
• Javascript

• // OJ: https://leetcode.com/problems/maximum-product-after-k-increments/
  // Time: O(NlogN)
  // Space: O(N)
  class Solution {
  public:
      int maximumProduct(vector<int>& A, int k) {
          long mod = 1e9 + 7, ans = 1;
          priority_queue<int, vector<int>, greater<>> pq(begin(A), end(A));
          while (k--) {
              int u = pq.top(), d = 1;
              pq.pop();
              pq.push(u + 1);
          }
          while (pq.size()) {
              ans = ans * pq.top() % mod;
              pq.pop();
          }
          return ans;
      }
  };
  

• class Solution:
      def maximumProduct(self, nums: List[int], k: int) -> int:
          heapify(nums)
          for _ in range(k):
              heappush(nums, heappop(nums) + 1)
          ans = 1
          mod = 10**9 + 7
          for v in nums:
              ans = (ans * v) % mod
          return ans
  
  ############
  
  # 2233. Maximum Product After K Increments
  # https://leetcode.com/problems/maximum-product-after-k-increments
  
  class Solution:
      def maximumProduct(self, nums: List[int], k: int) -> int:
          M = 10 ** 9 + 7
          pq = [x for x in nums]
          heapq.heapify(pq)
          
          while k > 0:
              x = heapq.heappop(pq) + 1
              heapq.heappush(pq, x)
              k -= 1
          
          x = 1
          
          for y in pq:
              x *= y
              x %= M
  
          return x
          
  
  

• class Solution {
      private static final int MOD = (int) 1e9 + 7;
  
      public int maximumProduct(int[] nums, int k) {
          PriorityQueue<Integer> q = new PriorityQueue<>();
          for (int v : nums) {
              q.offer(v);
          }
          while (k-- > 0) {
              q.offer(q.poll() + 1);
          }
          long ans = 1;
          while (!q.isEmpty()) {
              ans = (ans * q.poll()) % MOD;
          }
          return (int) ans;
      }
  }
  

• func maximumProduct(nums []int, k int) int {
  	h := hp{nums}
  	for heap.Init(&h); k > 0; k-- {
  		h.IntSlice[0]++
  		heap.Fix(&h, 0)
  	}
  	ans := 1
  	for _, v := range nums {
  		ans = (ans * v) % (1e9 + 7)
  	}
  	return ans
  }
  
  type hp struct{ sort.IntSlice }
  
  func (hp) Push(interface{})     {}
  func (hp) Pop() (_ interface{}) { return }
  

• /**
   * @param {number[]} nums
   * @param {number} k
   * @return {number}
   */
  var maximumProduct = function (nums, k) {
      const n = nums.length;
      let pq = new MinPriorityQueue();
      for (let i = 0; i < n; i++) {
          pq.enqueue(nums[i]);
      }
      for (let i = 0; i < k; i++) {
          pq.enqueue(pq.dequeue().element + 1);
      }
      let ans = 1;
      const limit = 10 ** 9 + 7;
      for (let i = 0; i < n; i++) {
          ans = (ans * pq.dequeue().element) % limit;
      }
      return ans;
  };
  
  

Solution 2. Binary Search

• C++
• Python
• Java
• Go
• Javascript

• // OJ: https://leetcode.com/problems/maximum-product-after-k-increments/
  // Time: O(NlogN)
  // Space: O(1)
  class Solution {
  public:
      int maximumProduct(vector<int>& A, int k) {
          long mod = 1e9 + 7, ans = 1, L = 0, R = LONG_MAX, r = 0;
          sort(begin(A), end(A));
          while (L <= R) { // After the binary search, R is the maximum number such that if we turn all A[i] < R to R, we take no more than `k` increments
              long M = L + (R - L) / 2, used = 0;
              for (int n : A) {
                  used += max(0L, M - n);
                  if (used > k) break;
              }
              if (used <= k) {
                  L = M + 1;
                  r = k - used; // `r` is the remainder increments
              } else R = M - 1;
          }
          for (int n : A) {
              int diff = min((long)k, max(0L, R - n));
              if (r) diff++, r--;
              k -= diff;
              ans = ans * (n + diff) % mod;
          }
          return ans;
      }
  };
  

• class Solution:
      def maximumProduct(self, nums: List[int], k: int) -> int:
          heapify(nums)
          for _ in range(k):
              heappush(nums, heappop(nums) + 1)
          ans = 1
          mod = 10**9 + 7
          for v in nums:
              ans = (ans * v) % mod
          return ans
  
  ############
  
  # 2233. Maximum Product After K Increments
  # https://leetcode.com/problems/maximum-product-after-k-increments
  
  class Solution:
      def maximumProduct(self, nums: List[int], k: int) -> int:
          M = 10 ** 9 + 7
          pq = [x for x in nums]
          heapq.heapify(pq)
          
          while k > 0:
              x = heapq.heappop(pq) + 1
              heapq.heappush(pq, x)
              k -= 1
          
          x = 1
          
          for y in pq:
              x *= y
              x %= M
  
          return x
          
  
  

• class Solution {
      private static final int MOD = (int) 1e9 + 7;
  
      public int maximumProduct(int[] nums, int k) {
          PriorityQueue<Integer> q = new PriorityQueue<>();
          for (int v : nums) {
              q.offer(v);
          }
          while (k-- > 0) {
              q.offer(q.poll() + 1);
          }
          long ans = 1;
          while (!q.isEmpty()) {
              ans = (ans * q.poll()) % MOD;
          }
          return (int) ans;
      }
  }
  

• func maximumProduct(nums []int, k int) int {
  	h := hp{nums}
  	for heap.Init(&h); k > 0; k-- {
  		h.IntSlice[0]++
  		heap.Fix(&h, 0)
  	}
  	ans := 1
  	for _, v := range nums {
  		ans = (ans * v) % (1e9 + 7)
  	}
  	return ans
  }
  
  type hp struct{ sort.IntSlice }
  
  func (hp) Push(interface{})     {}
  func (hp) Pop() (_ interface{}) { return }
  

• /**
   * @param {number[]} nums
   * @param {number} k
   * @return {number}
   */
  var maximumProduct = function (nums, k) {
      const n = nums.length;
      let pq = new MinPriorityQueue();
      for (let i = 0; i < n; i++) {
          pq.enqueue(nums[i]);
      }
      for (let i = 0; i < k; i++) {
          pq.enqueue(pq.dequeue().element + 1);
      }
      let ans = 1;
      const limit = 10 ** 9 + 7;
      for (let i = 0; i < n; i++) {
          ans = (ans * pq.dequeue().element) % limit;
      }
      return ans;
  };
  
  

Solution 3. Greedy

• C++
• Python
• Java
• Go
• Javascript

• // OJ: https://leetcode.com/problems/maximum-product-after-k-increments/
  // Time: O(NlogN)
  // Space: O(1)
  class Solution {
      void fillK(vector<int> &A, int k) {
          long N = A.size(), sum = 0, i = 0; 
          while (i < N && A[i] * i - sum <= k) sum += A[i++]; // If we bump `A[0]~A[i-1]` to be `A[i]`, we need `A[i] * i - (A[0]+...+A[i-1])` increments which should be no more than `k`
          int h = (sum + k) / i, r = (sum + k) % i;  // We split `sum + k` heights among `A[0]~A[i-1]` `i` elements.
          for (int j = 0; j < i; ++j) {
              A[j] = h; 
              if (j < r) A[j]++;
          }
      }
  public:
      int maximumProduct(vector<int>& A, int k) {
          long mod = 1e9 + 7, ans = 1;
          sort(begin(A), end(A));
          fillK(A, k);
          for (int n : A) ans = ans * n % mod;
          return ans;
      }
  };
  

• class Solution:
      def maximumProduct(self, nums: List[int], k: int) -> int:
          heapify(nums)
          for _ in range(k):
              heappush(nums, heappop(nums) + 1)
          ans = 1
          mod = 10**9 + 7
          for v in nums:
              ans = (ans * v) % mod
          return ans
  
  ############
  
  # 2233. Maximum Product After K Increments
  # https://leetcode.com/problems/maximum-product-after-k-increments
  
  class Solution:
      def maximumProduct(self, nums: List[int], k: int) -> int:
          M = 10 ** 9 + 7
          pq = [x for x in nums]
          heapq.heapify(pq)
          
          while k > 0:
              x = heapq.heappop(pq) + 1
              heapq.heappush(pq, x)
              k -= 1
          
          x = 1
          
          for y in pq:
              x *= y
              x %= M
  
          return x
          
  
  

• class Solution {
      private static final int MOD = (int) 1e9 + 7;
  
      public int maximumProduct(int[] nums, int k) {
          PriorityQueue<Integer> q = new PriorityQueue<>();
          for (int v : nums) {
              q.offer(v);
          }
          while (k-- > 0) {
              q.offer(q.poll() + 1);
          }
          long ans = 1;
          while (!q.isEmpty()) {
              ans = (ans * q.poll()) % MOD;
          }
          return (int) ans;
      }
  }
  

• func maximumProduct(nums []int, k int) int {
  	h := hp{nums}
  	for heap.Init(&h); k > 0; k-- {
  		h.IntSlice[0]++
  		heap.Fix(&h, 0)
  	}
  	ans := 1
  	for _, v := range nums {
  		ans = (ans * v) % (1e9 + 7)
  	}
  	return ans
  }
  
  type hp struct{ sort.IntSlice }
  
  func (hp) Push(interface{})     {}
  func (hp) Pop() (_ interface{}) { return }
  

• /**
   * @param {number[]} nums
   * @param {number} k
   * @return {number}
   */
  var maximumProduct = function (nums, k) {
      const n = nums.length;
      let pq = new MinPriorityQueue();
      for (let i = 0; i < n; i++) {
          pq.enqueue(nums[i]);
      }
      for (let i = 0; i < k; i++) {
          pq.enqueue(pq.dequeue().element + 1);
      }
      let ans = 1;
      const limit = 10 ** 9 + 7;
      for (let i = 0; i < n; i++) {
          ans = (ans * pq.dequeue().element) % limit;
      }
      return ans;
  };
  
  

Discuss

https://leetcode.com/problems/maximum-product-after-k-increments/discuss/1937658

All Problems

All Solutions