We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Increments for Target Multiples in an Array

Number: 3697

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given two arrays, nums and target, you can increment any element in nums by one per operation. The goal is to achieve the minimum total number of operations such that for every element t in target, there is at least one number in nums (after performing increments) that is a multiple of t.

Key Insights

  • Each number in nums can be incremented until it becomes a multiple of a given target value.
  • A single modified number might cover more than one target if it is a multiple of the least common multiple (LCM) of a subset of targets.
  • Since target’s size is at most 4, we can iterate over all non-empty subsets (up to 15) of target indices.
  • For each nums element and each non-empty subset of target, calculate the cost to increase the number to the smallest multiple of the LCM of that subset that is no less than the element.
  • Use dynamic programming (DP) with bitmask states (where each bit represents whether a target is covered) to combine the contributions of different nums elements optimally.

Space and Time Complexity

Time Complexity: O(N * 2^T * 2^T) where T <= 4, so effectively O(N) ≈ O(5×10^4) Space Complexity: O(2^T) = O(16)

Solution

The solution reduces to a minimum cost cover problem over a set of targets. For each number in nums, we:

  1. Compute the cost to convert it into a multiple of the LCM of every non-empty subset of targets.
  2. Use a DP array (indexed by a bitmask of length T) to track the minimum cost required to cover each subset of targets.
  3. For each number, update the DP states: for every current state (mask) and every possible subset that the current number can cover (with cost computed), update the state corresponding to the union of these targets.
  4. The final answer is found in the DP state corresponding to the full mask, i.e. all targets covered.

The “trick” is to realize that one incremented nums element may serve double duty by covering multiple target numbers simultaneously if it becomes a multiple of their LCM.

Code Solutions

import math

def lcm(a, b):
    # Compute the Least Common Multiple using GCD
    return a * b // math.gcd(a, b)

def min_increments_for_target_multiples(nums, target):
    t_size = len(target)
    full_mask = (1 << t_size) - 1

    # Precompute LCM for every nonempty subset of targets
    subset_lcm = {}
    for mask in range(1, 1 << t_size):
        current_lcm = 1
        for j in range(t_size):
            if mask & (1 << j):
                current_lcm = lcm(current_lcm, target[j])
        subset_lcm[mask] = current_lcm

    # dp[mask] will store the minimum cost to cover the targets in 'mask'
    dp = [float('inf')] * (1 << t_size)
    dp[0] = 0  # no cost to cover none

    # Process each number in nums
    for num in nums:
        new_dp = dp[:]  # copy current dp state; not using current num is an option
        for subset_mask, sub_lcm in subset_lcm.items():
            # Calculate cost to increment num to the next multiple of sub_lcm
            multiples = (num + sub_lcm - 1) // sub_lcm  # equivalent to ceil(num / sub_lcm)
            cost = multiples * sub_lcm - num
            # Update DP: combine current state with this option
            for cur_mask in range(1 << t_size):
                if dp[cur_mask] != float('inf'):
                    new_mask = cur_mask | subset_mask
                    new_dp[new_mask] = min(new_dp[new_mask], dp[cur_mask] + cost)
        dp = new_dp

    return dp[full_mask]

# Example usage:
if __name__ == "__main__":
    # Example 1
    nums = [1,2,3]
    target = [4]
    print(min_increments_for_target_multiples(nums, target))  # Expected Output: 1

    # Example 2
    nums = [8,4]
    target = [10,5]
    print(min_increments_for_target_multiples(nums, target))  # Expected Output: 2

    # Example 3
    nums = [7,9,10]
    target = [7]
    print(min_increments_for_target_multiples(nums, target))  # Expected Output: 0
← Back to All Questions