3444. Minimum Increments for Target Multiples in an Array LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3444. Minimum Increments for Target Multiples in an Array LeetCode Solution with the best time and space complexity. The solution to Minimum Increments for Target Multiples in an Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Minimum Increments for Target Multiples in an Array solution in C++
  4. Minimum Increments for Target Multiples in an Array solution in Java
  5. Minimum Increments for Target Multiples in an Array solution in Python
  6. Additional Resources
3444. Minimum Increments for Target Multiples in an Array LeetCode Solution image

Problem Statement of Minimum Increments for Target Multiples in an Array

You are given two arrays, nums and target.
In a single operation, you may increment any element of nums by 1.
Return the minimum number of operations required so that each element in target has at least one multiple in nums.

Example 1:

Input: nums = [1,2,3], target = [4]
Output: 1
Explanation:
The minimum number of operations required to satisfy the condition is 1.

Increment 3 to 4 with just one operation, making 4 a multiple of itself.

Example 2:

Input: nums = [8,4], target = [10,5]
Output: 2
Explanation:
The minimum number of operations required to satisfy the condition is 2.

Increment 8 to 10 with 2 operations, making 10 a multiple of both 5 and 10.

Example 3:

Input: nums = [7,9,10], target = [7]
Output: 0
Explanation:
Target 7 already has a multiple in nums, so no additional operations are needed.

Constraints:

1 <= nums.length <= 5 * 104
1 <= target.length <= 4
target.length <= nums.length
1 <= nums[i], target[i] <= 104

Complexity Analysis

  • Time Complexity: O(2^{|\texttt{target}|} \cdot n)
  • Space Complexity: O(2^{|\texttt{target}|} + n)

3444. Minimum Increments for Target Multiples in an Array LeetCode Solution in C++

class Solution {
 public:
  int minimumIncrements(vector<int>& nums, vector<int>& target) {
    const int maxMask = 1 << target.size();
    unordered_map<int, long> maskToLcm;

    for (int mask = 1; mask < maxMask; ++mask) {
      const vector<int> subset = getSubset(mask, target);
      maskToLcm[mask] = getLcm(subset);
    }

    // dp[mask] := the minimum number of increments to make each number in the
    // subset of target have at least one number that is a multiple in `num`,
    // where `mask` is the bitmask of the subset of target
    vector<long> dp(maxMask, LONG_MAX);
    dp[0] = 0;

    for (const int num : nums) {
      // maskToCost := (mask, cost), where `mask` is the bitmask of the subset
      // of target and `cost` is the minimum number of increments to make each
      // number in the subset of target have at least one number that is a
      // multiple in `num`
      vector<pair<int, long>> maskToCost;
      for (const auto& [mask, lcm] : maskToLcm) {
        const int remainder = num % lcm;
        maskToCost.emplace_back(mask, remainder == 0 ? 0 : lcm - remainder);
      }
      vector<long> newDp = dp;
      for (int prevMask = 0; prevMask < maxMask; ++prevMask) {
        if (dp[prevMask] == LONG_MAX)
          continue;
        for (const auto& [mask, cost] : maskToCost) {
          const int nextMask = prevMask | mask;
          newDp[nextMask] = min(newDp[nextMask], dp[prevMask] + cost);
        }
      }
      dp = std::move(newDp);
    }

    return dp.back() == LONG_MAX ? -1 : dp.back();
  }

 private:
  vector<int> getSubset(int mask, const vector<int>& target) {
    vector<int> subset;
    for (int i = 0; i < target.size(); ++i)
      if (mask >> i & 1)
        subset.push_back(target[i]);
    return subset;
  }

  long getLcm(const vector<int>& nums) {
    long res = 1;
    for (const int num : nums)
      res = lcm(res, num);
    return res;
  }
};
/* code provided by PROGIEZ */

3444. Minimum Increments for Target Multiples in an Array LeetCode Solution in Java

class Solution {
  public int minimumIncrements(int[] nums, int[] target) {
    final int maxMask = 1 << target.length;
    Map<Integer, Long> maskToLcm = new HashMap<>();

    for (int mask = 1; mask < maxMask; ++mask) {
      List<Integer> subset = getSubset(mask, target);
      maskToLcm.put(mask, getLcm(subset));
    }

    // dp[mask] := the minimum number of increments to make each number in the
    // subset of target have at least one number that is a multiple in `num`,
    // where `mask` is the bitmask of the subset of target
    long[] dp = new long[maxMask];
    Arrays.fill(dp, Long.MAX_VALUE);
    dp[0] = 0;

    for (final int num : nums) {
      // maskToCost := (mask, cost), where `mask` is the bitmask of the subset
      // of target and `cost` is the minimum number of increments to make each
      // number in the subset of target have at least one number that is a
      // multiple in `num`
      List<Pair<Integer, Long>> maskToCost = new ArrayList<>();
      for (Map.Entry<Integer, Long> entry : maskToLcm.entrySet()) {
        final int mask = entry.getKey();
        final long lcm = entry.getValue();
        final long remainder = num % lcm;
        maskToCost.add(new Pair<>(mask, remainder == 0 ? 0 : lcm - remainder));
      }
      long[] newDp = dp.clone();
      for (int prevMask = 0; prevMask < maxMask; ++prevMask) {
        if (dp[prevMask] == Long.MAX_VALUE)
          continue;
        for (Pair<Integer, Long> pair : maskToCost) {
          final int mask = pair.getKey();
          final long cost = pair.getValue();
          final int nextMask = prevMask | mask;
          newDp[nextMask] = Math.min(newDp[nextMask], dp[prevMask] + cost);
        }
      }
      dp = newDp;
    }

    return dp[maxMask - 1] == Long.MAX_VALUE ? -1 : (int) dp[maxMask - 1];
  }

  private List<Integer> getSubset(int mask, int[] target) {
    List<Integer> subset = new ArrayList<>();
    for (int i = 0; i < target.length; ++i)
      if ((mask >> i & 1) == 1)
        subset.add(target[i]);
    return subset;
  }

  private long getLcm(List<Integer> nums) {
    long res = 1;
    for (final int num : nums)
      res = lcm(res, num);
    return res;
  }

  private long lcm(long a, long b) {
    return a * b / gcd(a, b);
  }

  private long gcd(long a, long b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}
// code provided by PROGIEZ

3444. Minimum Increments for Target Multiples in an Array LeetCode Solution in Python

class Solution:
  def minimumIncrements(self, nums: list[int], target: list[int]) -> int:
    maxMask = 1 << len(target)
    maskToLcm = {}

    for mask in range(1, maxMask):
      subset = [num for i, num in enumerate(target) if mask >> i & 1]
      maskToLcm[mask] = functools.reduce(math.lcm, subset, 1)

    # dp[mask] := the minimum number of increments to make each number in the
    # subset of target have at least one number that is a multiple in `num`,
    # where `mask` is the bitmask of the subset of target
    dp = [math.inf] * maxMask
    dp[0] = 0

    for num in nums:
      # maskToCost := (mask, cost), where `mask` is the bitmask of the subset
      # of target and `cost` is the minimum number of increments to make each
      # number in the subset of target have at least one number that is a
      # multiple in `num`
      maskToCost = [
          (mask, 0 if (remainder := num % lcm) == 0 else lcm - remainder) for mask,
          lcm in maskToLcm.items()]
      newDp = dp[:]
      for prevMask in range(maxMask):
        if dp[prevMask] == float('inf'):
          continue
        for mask, cost in maskToCost:
          nextMask = prevMask | mask
          newDp[nextMask] = min(newDp[nextMask], dp[prevMask] + cost)
      dp = newDp

    return -1 if dp[-1] == math.inf else dp[-1]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.