2025-08-13：使数组包含目标值倍数的最少增量。用go语言，给出两个整数数组 nums 和 target。每一步可以把 nums 中的任意一个元素加 1。问至少需要多少次这样的加法操作，才能使得对 target 中的每一个值 t，最终的 nums 中都有至少一个数能够被 t 整除（即是 t 的倍数）。

1 <= nums.length <= 5 * 10000。

1 <= target.length <= 4。

target.length <= nums.length。

1 <= nums[i], target[i] <= 10000。

输入：nums = [8,4], target = [10,5]。

输出：2。

解释：

满足题目条件的最少操作次数是 2 。

将 8 增加到 10 ，需要 2 次操作，10 是目标值 5 和 10 的倍数。

题目来自力扣3444。

步骤描述

1. 预处理所有子集的最小公倍数（LCM）
  • 使用掩码表示 target 数组的子集（长度为 m，掩码范围 0 到 (1<<m)-1）。
  • 初始化 lcms[0] = 1（空集的 LCM 为 1）。
  • 遍历每个 target 元素 t（索引 i）：
    • 对于每个已处理的掩码 mask，计算新掩码 mask | (1<<i) 的 LCM = lcm(t, lcms[mask])。
  • 计算 lcm(a, b) 时，先求最大公约数（GCD），再用公式 a * b / GCD(a, b)（实际代码中为避免溢出，调整为 a / GCD(a, b) * b）。
  • 时间复杂度：O(2^m * m)，由于 m <= 4，最多 16 个子集，常数时间。

2. 确定最大 LCM 阈值

  • 计算 maxLcm = max(max(nums) * m, max(target))。
  • 理由：任何元素最多增加 m 次（最坏情况），且目标值最大为 max(target)，超过此阈值的 LCM 无法通过增量达到，故后续可忽略。

3. 收集候选索引

  • 初始化候选索引集合 candidateIndices（空集合）。
  • 遍历每个非空子集掩码（从 1 到 (1<<m)-1）：
    • 若当前子集的 LCM > maxLcm，跳过。
    • 否则，维护一个大小为 m 的最大堆（堆顶为最大增量）：
      • 遍历 nums 中每个元素 x：
        • 计算增量：(lcm - x % lcm) % lcm（若 x 已是 lcm 的倍数，增量为 0）。
        • 若堆未满，将 (增量, 索引) 加入堆；否则，若当前增量小于堆顶增量，替换堆顶。
    • 遍历结束后，将堆中所有索引加入 candidateIndices（自动去重）。
  • 时间复杂度：O(2^m * n)，其中 2^m 为子集数（最多 15），n 为 nums 长度。

4. 动态规划求解最小操作次数

  • 状态定义：f[mask] 表示满足掩码 mask 对应的子集（mask 的二进制位表示 target 元素是否被满足）所需的最小操作次数。
  • 初始化：
    • f[0] = 0（空集无需操作）。
    • 其他 f[mask] = 大数（如 math.MaxInt/2）。
  • 状态转移：
    • 遍历每个候选索引 i（来自 candidateIndices）：
      • 从大到小遍历状态 j（从 (1<<m)-1 到 1）：
        • 枚举 j 的非空子集 sub（通过 sub = (sub-1) & j 迭代）：
          • 计算增量：(lcms[sub] - nums[i] % lcms[sub]) % lcms[sub]。
          • 更新：f[j] = min(f[j], f[j^sub] + 增量)。
  • 目标：f[(1<<m)-1]（所有 target 元素均被满足）。
  • 时间复杂度：O(|C| * 2^m * 2^m)，其中 |C| 为候选索引数（最多 64），2^m 为状态数（最多 16），子集枚举最多 2^m 次（常数）。

5. 返回结果

  • 输出 f[(1<<m)-1] 作为最小操作次数。

复杂度分析

  • 总时间复杂度：
    • 预处理 LCM：O(2^m * m) = O(16 * 4) = O(1)。
    • 收集候选索引：O(2^m * n) = O(15 * n) ≈ O(n)。
    • 动态规划：O(|C| * 2^{2m}) = O(64 * 256) = O(1)。
    • 整体：O(n)（线性）。
  • 总额外空间复杂度：
    • LCM 数组：O(2^m) = O(16)。
    • 候选索引集合：O(2^m * m) = O(64)。
    • 堆：O(m) = O(4)。
    • 动态规划数组：O(2^m) = O(16)。
    • 整体：O(1)（常数空间，不依赖输入规模）。

示例说明

  • 输入：nums = [8, 4], target = [10, 5]。
  • 处理：
    1. 子集 LCM：{}:1, {10}:10, {5}:5, {10,5}:10。
    2. maxLcm = max(8*2, 10) = 16（全部保留）。
    3. 候选索引：
      • LCM=10：堆中索引 0（增量 2）、1（增量 6）。
      • LCM=5：堆中索引 0（增量 2）、1（增量 1）→ 加入索引 0,1。
    4. 动态规划：
      • 初始 f[00]=0, 其他无穷大。
      • 索引 0（元素 8）：
        • j=11：子集 11 → f[11]=min(∞, f[00]+2)=2。
        • j=10：子集 10 → f[10]=min(∞, f[00]+2)=2。
        • j=01：子集 01 → f[01]=min(∞, f[00]+2)=2。
      • 索引 1（元素 4）：
        • j=11：子集 11 → f[11]=min(2, f[00]+6)=2（不变）。
        • j=10：子集 10 → f[10]=min(2, f[00]+1)=1。
        • j=01：子集 01 → f[01]=min(2, f[00]+6)=2（不变）。
      • 最终 f[11]=2。
  • 输出：2。

Go完整代码如下：

package mainimport ("container/heap""fmt""math""slices"
)func minimumIncrements(nums []int, target []int) int {m := len(target)lcms := make([]int, 1<<m)lcms[0] = 1for i, t := range target {bit := 1 << ifor mask, l := range lcms[:bit] {lcms[bit|mask] = lcm(t, l)}}maxLcm := max(slices.Max(nums)*m, slices.Max(target))candidateIndices := map[int]struct{}{}for _, l := range lcms[1:] {if l > maxLcm {continue}h := hp{}for i, x := range nums {p := pair{(l - x%l) % l, i}if len(h) < m {heap.Push(&h, p)} else {h.update(p)}}for _, p := range h {candidateIndices[p.i] = struct{}{}}}f := make([]int, 1<<m)for j := 1; j < 1<<m; j++ {f[j] = math.MaxInt / 2}for i := range candidateIndices {x := nums[i]for j := 1<<m - 1; j > 0; j-- {for sub := j; sub > 0; sub = (sub - 1) & j {l := lcms[sub]f[j] = min(f[j], f[j^sub]+(l-x%l)%l)}}}return f[1<<m-1]
}func gcd(a, b int) int {for a != 0 {a, b = b%a, a}return b
}
func lcm(a, b int) int { return a / gcd(a, b) * b }type pair struct{ op, i int }
type hp []pairfunc (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].op > h[j].op }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(pair)) }
func (hp) Pop() (_ any)         { return }
func (h *hp) update(p pair) {if p.op < (*h)[0].op {(*h)[0] = pheap.Fix(h, 0)}
}func main() {nums := []int{8, 4}target := []int{10, 5}result := minimumIncrements(nums, target)fmt.Println(result)
}

在这里插入图片描述

Python完整代码如下：

# -*-coding:utf-8-*-import heapq
import math
from math import gcd
from typing import Listdef lcm(a: int, b: int) -> int:return a * b // gcd(a, b)def minimum_increments(nums: List[int], target: List[int]) -> int:m = len(target)n = len(nums)total_mask = 1 << m# 计算所有子集的最小公倍数lcms = [1] * total_maskfor i in range(m):bit = 1 << ifor mask in range(bit):new_mask = mask | bitlcms[new_mask] = lcm(lcms[mask], target[i])# 计算最大LCM用于过滤max_lcm_val = max(max(nums) * m, max(target))# 收集候选索引candidate_set = set()for mask in range(1, total_mask):l_val = lcms[mask]if l_val > max_lcm_val:continueheap = []for idx, x in enumerate(nums):cost = (l_val - x % l_val) % l_valif len(heap) < m:heapq.heappush(heap, (-cost, idx))else:if cost < -heap[0][0]:heapq.heapreplace(heap, (-cost, idx))for neg_cost, idx in heap:candidate_set.add(idx)# 动态规划f = [10**18] * total_maskf[0] = 0for idx in candidate_set:x = nums[idx]# 倒序遍历所有状态for j in range(total_mask - 1, 0, -1):# 枚举所有非空子集sub = jwhile sub > 0:l_val = lcms[sub]cost = (l_val - x % l_val) % l_valprev_state = j ^ subif f[prev_state] + cost < f[j]:f[j] = f[prev_state] + costsub = (sub - 1) & jreturn f[total_mask - 1]# 测试用例
if __name__ == "__main__":nums = [8, 4]target = [10, 5]print(minimum_increments(nums, target))  # 输出: 3

在这里插入图片描述