Scale Engineer

Minimum Increments for Target Multiples in an Array

Hard
#3061Time: O((2^k)^N), where N is `nums.length` and k is `target.length`. For each of the N numbers, we can choose to use it for any of the `2^k-1` subsets of targets or not use it, leading to roughly `2^k` choices per number. This is prohibitively slow.Space: O(N) for the recursion stack depth, where N is the length of `nums`.
Patterns
MathDynamic ProgrammingBit ManipulationNumber TheoryBitmask
Data structures
Array

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

A brute-force approach systematically explores every possible assignment of nums elements to cover subsets of target elements. This can be formulated as a recursive backtracking algorithm. For each number in nums, we decide whether to use it to cover a specific subset of the yet-unsatisfied targets or to not use it at all. This process continues until all targets are covered or all numbers from nums have been considered.

Algorithm

  • Define a recursive function, say solve(index, mask), which returns the minimum cost to satisfy the targets represented by the bits not set in mask, using numbers from nums[index] onwards.
  • The mask is a bitmask of length k (where k is target.length), representing the subset of satisfied target elements.
  • Base Cases:
    • If mask has all k bits set, all targets are satisfied. Return 0.
    • If index reaches the end of nums but mask is not yet full, it's impossible to satisfy the remaining targets. Return a very large value (infinity).
  • Recursive Step: For the number nums[index], we have several choices:
    1. Skip nums[index]: Don't use it. The cost is solve(index + 1, mask).
    2. Use nums[index]: Use it to satisfy a non-empty subset of the currently unsatisfied targets. Iterate through all non-empty submasks submask of the uncovered_targets.
      • Calculate the cost to make nums[index] a common multiple of all targets in submask. This requires finding the least common multiple (LCM) of these targets, let's call it L. The cost is (L - (nums[index] % L)) % L.
      • The total cost for this choice is this calculated cost plus the result of the recursive call solve(index + 1, mask | submask).
  • The function returns the minimum cost found among all possible choices.

Walkthrough

The core of this method is a recursive function that builds a solution step-by-step. The state of the recursion is typically defined by (index, mask), where index tracks the current element in nums being considered, and mask is a bitmask indicating which target elements have been satisfied.

At each step index, the function branches out. One branch corresponds to skipping nums[index]. The other branches correspond to using nums[index] to satisfy any combination of the remaining targets. This creates a vast search tree of possibilities. The cost for using nums[index] to satisfy a set of targets is the number of increments required to make it a common multiple of them. The final answer is the minimum cost found across all paths in the search tree that successfully cover all targets.

import java.util.Arrays; class Solution {    private int[] target;    private int k;    private long[][] memo;    private long[] lcmOfMask;     public int minimumValueSum(int[] nums, int[] target) {        this.target = target;        this.k = target.length;        this.memo = new long[nums.length][1 << k];        for (long[] row : memo) {            Arrays.fill(row, -1);        }         // Precompute LCMs for all masks        this.lcmOfMask = new long[1 << k];        for (int mask = 1; mask < (1 << k); mask++) {            long currentLcm = 1;            for (int i = 0; i < k; i++) {                if ((mask & (1 << i)) != 0) {                    currentLcm = lcm(currentLcm, this.target[i]);                }            }            lcmOfMask[mask] = currentLcm;        }         long result = solve(nums, 0, 0);        return result >= Long.MAX_VALUE / 2 ? -1 : (int) result; // Assuming -1 for impossible    }     private long solve(int[] nums, int index, int mask) {        if (mask == (1 << k) - 1) {            return 0;        }        if (index == nums.length) {            return Long.MAX_VALUE / 2; // Represents infinity        }         // This is the unmemoized version. With memoization, it becomes the DP approach.        // if (memo[index][mask] != -1) {        //     return memo[index][mask];        // }         // Choice 1: Skip nums[index]        long minCost = solve(nums, index + 1, mask);         // Choice 2: Use nums[index] to cover a subset of remaining targets        int uncoveredMask = ((1 << k) - 1) & ~mask;        for (int submask = uncoveredMask; submask > 0; submask = (submask - 1) & uncoveredMask) {            long l = lcmOfMask[submask];            long currentNum = nums[index];            long cost = (l - (currentNum % l)) % l;                        long remainingCost = solve(nums, index + 1, mask | submask);            if (remainingCost < Long.MAX_VALUE / 2) {                minCost = Math.min(minCost, cost + remainingCost);            }        }         // return memo[index][mask] = minCost;        return minCost;    }     private long gcd(long a, long b) {        while (b > 0) {            long temp = b;            b = a % b;            a = temp;        }        return a;    }     private long lcm(long a, long b) {        if (a == 0 || b == 0) return 0;        return Math.abs(a * b) / gcd(a, b);    }}

Complexity

Time

O((2^k)^N), where N is `nums.length` and k is `target.length`. For each of the N numbers, we can choose to use it for any of the `2^k-1` subsets of targets or not use it, leading to roughly `2^k` choices per number. This is prohibitively slow.

Space

O(N) for the recursion stack depth, where N is the length of `nums`.

Trade-offs

Pros

  • Conceptually simple and follows a natural decision-making process.

Cons

  • Extremely inefficient due to the massive number of redundant computations for the same subproblems (index, mask).

  • Guaranteed to receive a 'Time Limit Exceeded' (TLE) verdict on any reasonably large test case.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem