algorithm - 找到每个 K 使得 arr[i]%K 等于每个 arr[i]

Question

我有一个 M 整数数组。我必须找到所有可能的整数 K(假设至少有 1 K)这样:

1) K > 1
2) arr[0]%K = arr[1]%K = arr[2]%K = ... = arr[M-1]%K 

这个问题的最佳算法是什么？

Answer 1

首先，让我们检查给定值。

• 假设至少存在一个K ，我们知道，例如，数组 arr这样 arr[0]=4; arr[1]=6; arr[2]=9 无效，因为没有模数给出每个相同的结果。
• 鉴于K > 1，我们知道数组的所有值不可能都相同。然而，它们是相同的 modK对于所有 K .

请记住 arr[i]%K (对于满足 0=<i<M 的任何 i )不一定是正数。

提出的算法

代码没有经过测试

在我看来，这似乎是确定 K 的最简单方法值将来自查找数组中每个值之间的差异。 (我将用 Java 显示示例。)假设 arrDiff包含每个值的差异，使得

arrDiff[0] = arr[0]-arr[1];
arrDiff[1] = arr[1] - arr[2];
...
arrDiff[M-1] = arr[M-1] - arr[0];

现在，找到G = gcd(arrDiff[0],arrDiff[1],...,arrDiff[M-1]找到所有有效的 K .你可以使用任何 gcd您想要的方法，即 Euclidean Algorithm , 为了迭代/递归地找到 G .您也可以忽略自 gcd 以来的负差异会给你积极的结果。

[All of G's factors]>1 (包括 G 本身)将有效 K值(value)观。

遍历

我不打算证明(我会留给你)，但为了清楚起见，让我们举个例子。

初始化一个例子arr

//Let's do an easy one with M=3
int arr[] = new int[3];
arr[0] = -7;
arr[1] = 9;
arr[2] = 25

创建差异数组

我将在这里展示一个稍微更有效的实现(感谢@RBarryYoung)。

int min = findSmallestNumber(arr); //Returns min value (may be negative)
//The array size is intended to not include the minimum, assuming we have no duplicates.
int arrDiff[] = new int[arr.length-1];
for(int num : arr){
    if(num==min) continue; 
    arrDiff[num] = arr[num] - min;
}

对于上面的例子，这段代码应该给我们 16,32 的值在 arrDiff .请注意，使用此方法应该会在下一步的 gcd 计算中产生所有正值。

计算G = gcd

我不会为您编写 gcd 方法，因为有很多实现；我假设你有一个方法 int gcd(int a, int b) .

int g = gcd(arrDiff[0], arrDiff[1]);
for(int i = 2, i < arrDiff.length-1, i++){
    g = gcd(g, arrDiff[i]);
}
//return g; 

请注意，如果数组中只有两个值，则没有 gcd用法是必要的——只需使用单一差异即可。

检查示例

对于我们的示例，您可以很容易地发现 gcd(-16,-16,32)=gcd(16,16,32)=16。因此 16 及其所有大于 1 的因子应该是答案。让我们至少检查 16 个。请注意，下面的“=”实际上应该是同余符号(三个竖条而不是两个)。

-7mod16 = 9mod16

9mod16 = 9mod16

25mod16 = 9mod16

您可以检查这是否也适用于因子 2,4,8 . (对于所有这些因素，您应该得到 1mod8 => 1mod4 => 1mod2。)

总结

如果您必须在代码中找到这些因素，您可能会对各种 factoring algorithms 中的一种感兴趣。找到 G 的所有因子大于 1。选择最优化可能取决于您的数据。

因此，它实际上是您可能需要的算法的组合。可能有更快的方法来执行我上面向您展示的操作，但基本算法现在应该很容易理解。