面试算法题：使数组所有元素拥有≥2公约数的最小增量求解

阿华AIGC实验室

2026-4-30

寻找数组最小增量达成公共≥2公约数的更优解法

问题描述

我最近面试遇到了这样一道算法题：

给定一个数组X = [X₁, X₂, ...., Xₙ]，其中每个元素满足1 ≤ i ≤ n，Xᵢ ≤ 500。需要对数组元素进行正增量操作（只能增加数值，不能减少），使得数组中所有元素拥有一个≥2的公约数，且所有增量的总和最小。
举个例子：
当X = [5, 7, 7, 7, 7]时，最优新数组是[7, 7, 7, 7, 7]，仅需给第一个元素加2，总增量为2；
而如果改成公约数为2的数组[6, 8, 8, 8, 8]，总增量是6，显然不是最优解。

我当前的解法

我想到了一个可行的解法，并且通过了所有测试用例。核心思路是：
因为最终数组的公共公约数≥2，那么这个公约数的某个质因数必然也是所有元素的公约数（比如如果公共公约数是6，那么质因数2或3也能整除所有元素），所以只需要遍历所有小于500的质数，针对每个质数计算将数组所有元素升级到最近的该质数倍数所需的总增量，最后取所有情况中的最小值。

具体实现代码如下（Python风格）：

def closest_multiple(x, y):
    # 用整数运算实现ceil(x/y)*y，避免浮点精度问题
    return ((x + y - 1) // y) * y

def min_total_increment(X):
    # 预生成所有小于500的质数，这里省略质数生成逻辑（比如用埃氏筛法）
    primes_less_than_500 = generate_primes(500)
    min_increment = float('inf')
    for prime in primes_less_than_500:
        total = 0
        for num in X:
            total += closest_multiple(num, prime) - num
        if total < min_increment:
            min_increment = total
    return min_increment

这个解法的时间复杂度本质上是O(n)，因为小于500的质数只有95个，常数级的遍历次数对n来说可以忽略。