使所有元素都有公约数的最小增量数
Minimum number of increments so that all elements have a common divisor
我最近在面试中遇到了这个问题：
给定一组数字 X = [X_1, X_2, ...., X_n]，其中 X_i <= 500 对应 1 <= i <= n。增加集合中的数字（仅正增量），使集合中的每个元素都有一个公约数 >=2，并且使所有增量的总和最小化。
例如，如果 X = [5, 7, 7, 7, 7] 新集合将是 X = [7, 7, 7, 7, 7] 因为您可以将 2 添加到 X_1。 X = [6, 8, 8, 8, 8] 的公分母是 2，但不正确，因为我们要加 6（将 2 加到 5，将 1 加到 4 个 7 中的每一个）。
我有一个看似可行的解决方案（因为它通过了所有测试用例）循环遍历小于 500 的素数，并且对于 X 中的每个 X_i 找到最接近的素数倍数大于 X_i.
的数字
function closest_multiple(x, y)
return ceil(x/y)*y
min_increment = inf
for each prime_number < 500:
total_increment = 0
for each element X_i in X:
total_increment += closest_multiple(X_i, prime_number) - X_i
min_increment = min(min_increment, total_increment)
return min_increment
技术上是 O(n)，但有更好的方法来解决这个问题吗？有人建议我使用动态规划，但我不确定它如何适合这里。
常量有界条目案例
当 X_i 受常数限制时，您可以渐进地实现的最佳时间是 O(n)，因为读取所有输入至少需要那么长时间。有一些实用的改进：
- 过滤掉重复项，这样您就可以使用（元素、频率）对列表。
- 提前停止循环。
closest_multiple(x, p) - x 的计算速度更快。这略微 hardware/language 相关，但单个整数模运算几乎肯定比 int -> float 转换、float 除法、ceiling() 调用和相同数量级的乘法更快。
freq_counts <- Initialize-Counter(X) // List of (element, freq) pairs
min_increment = inf
for each prime_number < 500:
total_increment = 0
for each pair X_i, freq in freq_counts:
total_increment += (prime_number - (X_i % prime_number)) * freq
if total_increment >= min_increment: break
min_increment = min(min_increment, total_increment)
return min_increment
大条目案例
对于均匀选择的随机数据，答案几乎总是使用“2”作为除数，而更大的素数几乎不可能。但是，让我们解决最坏的情况。
在这里，让 max(X) = M，这样我们的输入大小就是 O(n (log M)) 位。我们想要一个在该输入大小上是次指数的解决方案，因此找到所有低于 M（甚至 sqrt(M)）的素数是不可能的。我们正在寻找任何给我们 min-total-increment 的素数；我们称这样的素数为 min-prime。找到这样一个质数后，我们可以在线性时间内得到最小总增量。我们将使用分解方法和两个观察结果。
观察1：答案总是至多n，因为素数2整除X_i所需的增量至多为1。
观察 2：对于我们的大部分条目 X_i，我们试图找到除 X_i 或略大于 X_i 的数的素数.令 Consecutive-Product-Divisors[i] 为除 X_i or X_i+1 之一的所有素数的集合，我将其缩写为 CPD[i]。这正是整除 X_i * (1 + X_i).
的所有素数的集合
(Obs. 2 Continued) 如果 U 是我们答案的已知上限（此处最多为 n），并且 p是 X 的最小素数，那么 p 必须将 X_i 或 X_i + 1 除以至少 N - U/2 我们的 CPD 条目。使用 CPD 数组上的频率计数来查找所有此类素数。
一旦你有了候选素数列表（所有最小素数都保证在这个列表中），你就可以使用你的算法单独测试每个素数。由于数字 k 最多可以有 O(log k) 个不同的素数除数，这给出了 O(n log M) 个可能的不同素数，它们至少可以除掉一半的数字
[X_1*(1 + X_1), X_2*(1 + X_2), ... X_n*(1 + X_n)] 组成了我们的候选名单。您可以通过更仔细的分析来降低此界限，但它可能不会强烈影响整个算法的渐近运行时间。
大型条目的更优化复杂度
这个解决方案的复杂性很难用简短的形式写出来，因为瓶颈是分解 n 个最大大小 M 的数字，加上 O(n^2 log M) 算术（即加法、减法, multiplo, modulo) 对最大大小 M 的数字进行运算。这并不意味着运行时间未知：如果您 select 任何整数因式分解算法和大整数算术算法，您都可以准确地推导出运行时间。不幸的是，由于因式分解，上述算法最著名的运行时间是超多项式（但次指数）。
我们怎样才能做得更好？我确实找到了一个更复杂的解决方案，它基于最大公约数 (GCD) 和在多项式时间内运行的类似动态编程（尽管在非天文大小的输入上可能慢得多），因为它不依赖于因式分解。
解决方案依赖于以下两个陈述中至少有一个为真：
- 数
2 是 X 的最小素数，或者
- 对于
i、1 <= i <= n 的至少一个值，存在一个最优解，其中 X_i 保持不变，即 X_i 的一个除数产生一个最小总增量。
基于GCD的多项式时间算法
我们可以快速测试 2 和所有小素数的最低成本。事实上，我们将测试所有素数 p，p <= n，我们可以在多项式时间内完成，并从 X_i 及其前 n 个增量中分解出这些素数。这使我们得出以下算法：
// Given: input list X = [X_1, X_2, ... X_n].
// Subroutine compute-min-cost(list A, int p) is
// just the inner loop of the above algorithm.
min_increment = inf;
for each prime p <= n:
min_increment = min(min_increment, compute-min-cost(X, p));
// Initialize empty, 2-D, n x (n+1) list Y[n][n+1], of offset X-values
for all 1 <= i <= n:
for all 0 <= j <= n:
Y[i][j] <- X[i] + j;
for each prime p <= n: // Factor out all small prime divisors from Y
for each Y[i][j]:
while Y[i][j] % p == 0:
Y[i][j] /= p;
for all 1 <= i <= n: // Loop 1
// Y[i][0] is the test 'unincremented' entry
// Initialize empty hash-tables 'costs' and 'new_costs'
// Keys of hash-tables are GCDs,
// Values are a running sum of increment-costs for that GCD
costs[Y[i][0]] = 0;
for all 1 <= k <= n: // Loop 2
if i == k: continue;
clear all entries from new_costs // or reinitialize to empty
for all 0 <= j < n: // Loop 3
for each Key in costs: // Loop 4
g = GCD(Key, Y[k][j]);
if g == 1: continue;
if g is not a key in new_costs:
new_costs[g] = j + costs[Key];
else:
new_costs[g] = min(new_costs[g], j + costs[Key]);
swap(costs, new_costs);
if costs is not empty:
min_increment = min(min_increment, smallest Value in costs);
return min_increment;
这个解决方案的正确性来自前两个观察结果，以及（未经证实，但直截了当的）事实是有一个列表
[X_1 + r_1, X_2 + r_2, ... , X_n + r_n]（所有 i 的 0 <= r_i <= n）其 GCD 是具有最小增量成本的除数。
此解决方案的运行时更棘手：GCD 可以在 O(log^2(M)) 时间内轻松计算，并且可以在 poly(n) 时间内计算最多 n 的所有素数列表.从算法的循环结构来看，要证明整个算法的一个多项式界，只要证明我们的'costs' hash-table的最大尺寸是log M中的多项式即可。这就是小素数 'factoring-out' 发挥作用的地方。循环2迭代k后，costs中的条目是(Key, Value)对，其中每个Key是k + 1个元素的GCD：
我们最初的 Y[i][0] 和 [Y[1][j_1], Y[2][j_2], ... Y[k][j_k]] 一些 0 <= j_l < n。此键的值是此除数所需的最小增量总和（即 j_l 的总和）超过 j_l.
的所有可能选择
Y[i][0] 最多有 O(log M) 个唯一的质因数。在任何时候，每个这样的质数最多可以除掉我们 'costs' table 中的一个键：因为我们已经分解出低于 n 的所有质数因数，任何剩余的质数因数 p 都可以在任何 Y[j] = [X_j, 1 + X_j, ... n-1 + X_j] 中最多除以 n 个连续数字中的一个。这意味着整个算法是多项式的，并且运行时间低于 O(n^4 log^3(M)).
从这里开始，悬而未决的问题是是否存在更简单的算法，以及您能比这个界限好多少。您绝对可以优化此算法（包括使用之前的提前停止和频率计数）。也有可能更好地计算连续数字的大且不同的素数除数表明这个解决方案已经比规定的运行时间更好，但是这个解决方案的简化将非常有趣。
我最近在面试中遇到了这个问题：
给定一组数字 X = [X_1, X_2, ...., X_n]，其中 X_i <= 500 对应 1 <= i <= n。增加集合中的数字（仅正增量），使集合中的每个元素都有一个公约数 >=2，并且使所有增量的总和最小化。
例如，如果 X = [5, 7, 7, 7, 7] 新集合将是 X = [7, 7, 7, 7, 7] 因为您可以将 2 添加到 X_1。 X = [6, 8, 8, 8, 8] 的公分母是 2，但不正确，因为我们要加 6（将 2 加到 5，将 1 加到 4 个 7 中的每一个）。
我有一个看似可行的解决方案（因为它通过了所有测试用例）循环遍历小于 500 的素数，并且对于 X 中的每个 X_i 找到最接近的素数倍数大于 X_i.
function closest_multiple(x, y)
return ceil(x/y)*y
min_increment = inf
for each prime_number < 500:
total_increment = 0
for each element X_i in X:
total_increment += closest_multiple(X_i, prime_number) - X_i
min_increment = min(min_increment, total_increment)
return min_increment
技术上是 O(n)，但有更好的方法来解决这个问题吗？有人建议我使用动态规划，但我不确定它如何适合这里。
常量有界条目案例
当 X_i 受常数限制时，您可以渐进地实现的最佳时间是 O(n)，因为读取所有输入至少需要那么长时间。有一些实用的改进：
- 过滤掉重复项，这样您就可以使用（元素、频率）对列表。
- 提前停止循环。
closest_multiple(x, p) - x的计算速度更快。这略微 hardware/language 相关，但单个整数模运算几乎肯定比 int -> float 转换、float 除法、ceiling() 调用和相同数量级的乘法更快。
freq_counts <- Initialize-Counter(X) // List of (element, freq) pairs
min_increment = inf
for each prime_number < 500:
total_increment = 0
for each pair X_i, freq in freq_counts:
total_increment += (prime_number - (X_i % prime_number)) * freq
if total_increment >= min_increment: break
min_increment = min(min_increment, total_increment)
return min_increment
大条目案例
对于均匀选择的随机数据，答案几乎总是使用“2”作为除数，而更大的素数几乎不可能。但是，让我们解决最坏的情况。
在这里，让 max(X) = M，这样我们的输入大小就是 O(n (log M)) 位。我们想要一个在该输入大小上是次指数的解决方案，因此找到所有低于 M（甚至 sqrt(M)）的素数是不可能的。我们正在寻找任何给我们 min-total-increment 的素数；我们称这样的素数为 min-prime。找到这样一个质数后，我们可以在线性时间内得到最小总增量。我们将使用分解方法和两个观察结果。
观察1：答案总是至多
n，因为素数2整除X_i所需的增量至多为1。观察 2：对于我们的大部分条目
的所有素数的集合X_i，我们试图找到除X_i或略大于X_i的数的素数.令Consecutive-Product-Divisors[i]为除X_i or X_i+1之一的所有素数的集合，我将其缩写为 CPD[i]。这正是整除X_i * (1 + X_i).(Obs. 2 Continued) 如果 U 是我们答案的已知上限（此处最多为 n），并且
p是 X 的最小素数，那么p必须将X_i或X_i + 1除以至少N - U/2我们的 CPD 条目。使用 CPD 数组上的频率计数来查找所有此类素数。
一旦你有了候选素数列表（所有最小素数都保证在这个列表中），你就可以使用你的算法单独测试每个素数。由于数字 k 最多可以有 O(log k) 个不同的素数除数，这给出了 O(n log M) 个可能的不同素数，它们至少可以除掉一半的数字
[X_1*(1 + X_1), X_2*(1 + X_2), ... X_n*(1 + X_n)] 组成了我们的候选名单。您可以通过更仔细的分析来降低此界限，但它可能不会强烈影响整个算法的渐近运行时间。
大型条目的更优化复杂度
这个解决方案的复杂性很难用简短的形式写出来，因为瓶颈是分解 n 个最大大小 M 的数字，加上 O(n^2 log M) 算术（即加法、减法, multiplo, modulo) 对最大大小 M 的数字进行运算。这并不意味着运行时间未知：如果您 select 任何整数因式分解算法和大整数算术算法，您都可以准确地推导出运行时间。不幸的是，由于因式分解，上述算法最著名的运行时间是超多项式（但次指数）。
我们怎样才能做得更好？我确实找到了一个更复杂的解决方案，它基于最大公约数 (GCD) 和在多项式时间内运行的类似动态编程（尽管在非天文大小的输入上可能慢得多），因为它不依赖于因式分解。
解决方案依赖于以下两个陈述中至少有一个为真：
- 数
2是 X 的最小素数，或者 - 对于
i、1 <= i <= n的至少一个值，存在一个最优解，其中X_i保持不变，即X_i的一个除数产生一个最小总增量。
基于GCD的多项式时间算法
我们可以快速测试 2 和所有小素数的最低成本。事实上，我们将测试所有素数 p，p <= n，我们可以在多项式时间内完成，并从 X_i 及其前 n 个增量中分解出这些素数。这使我们得出以下算法：
// Given: input list X = [X_1, X_2, ... X_n].
// Subroutine compute-min-cost(list A, int p) is
// just the inner loop of the above algorithm.
min_increment = inf;
for each prime p <= n:
min_increment = min(min_increment, compute-min-cost(X, p));
// Initialize empty, 2-D, n x (n+1) list Y[n][n+1], of offset X-values
for all 1 <= i <= n:
for all 0 <= j <= n:
Y[i][j] <- X[i] + j;
for each prime p <= n: // Factor out all small prime divisors from Y
for each Y[i][j]:
while Y[i][j] % p == 0:
Y[i][j] /= p;
for all 1 <= i <= n: // Loop 1
// Y[i][0] is the test 'unincremented' entry
// Initialize empty hash-tables 'costs' and 'new_costs'
// Keys of hash-tables are GCDs,
// Values are a running sum of increment-costs for that GCD
costs[Y[i][0]] = 0;
for all 1 <= k <= n: // Loop 2
if i == k: continue;
clear all entries from new_costs // or reinitialize to empty
for all 0 <= j < n: // Loop 3
for each Key in costs: // Loop 4
g = GCD(Key, Y[k][j]);
if g == 1: continue;
if g is not a key in new_costs:
new_costs[g] = j + costs[Key];
else:
new_costs[g] = min(new_costs[g], j + costs[Key]);
swap(costs, new_costs);
if costs is not empty:
min_increment = min(min_increment, smallest Value in costs);
return min_increment;
这个解决方案的正确性来自前两个观察结果，以及（未经证实，但直截了当的）事实是有一个列表
[X_1 + r_1, X_2 + r_2, ... , X_n + r_n]（所有 i 的 0 <= r_i <= n）其 GCD 是具有最小增量成本的除数。
此解决方案的运行时更棘手：GCD 可以在 O(log^2(M)) 时间内轻松计算，并且可以在 poly(n) 时间内计算最多 n 的所有素数列表.从算法的循环结构来看，要证明整个算法的一个多项式界，只要证明我们的'costs' hash-table的最大尺寸是log M中的多项式即可。这就是小素数 'factoring-out' 发挥作用的地方。循环2迭代k后，costs中的条目是(Key, Value)对，其中每个Key是k + 1个元素的GCD：
我们最初的 Y[i][0] 和 [Y[1][j_1], Y[2][j_2], ... Y[k][j_k]] 一些 0 <= j_l < n。此键的值是此除数所需的最小增量总和（即 j_l 的总和）超过 j_l.
Y[i][0] 最多有 O(log M) 个唯一的质因数。在任何时候，每个这样的质数最多可以除掉我们 'costs' table 中的一个键：因为我们已经分解出低于 n 的所有质数因数，任何剩余的质数因数 p 都可以在任何 Y[j] = [X_j, 1 + X_j, ... n-1 + X_j] 中最多除以 n 个连续数字中的一个。这意味着整个算法是多项式的，并且运行时间低于 O(n^4 log^3(M)).
从这里开始，悬而未决的问题是是否存在更简单的算法，以及您能比这个界限好多少。您绝对可以优化此算法（包括使用之前的提前停止和频率计数）。也有可能更好地计算连续数字的大且不同的素数除数表明这个解决方案已经比规定的运行时间更好，但是这个解决方案的简化将非常有趣。