java - 最大数量的连续奇数等于一个目标

Question

我目前正在寻找最大数量的连续奇数加在一起等于目标数。

我当前查找 3 个连续整数的代码如下所示

public class consecutiveOdd {
    public static void main(String[] args){
        int target = 160701;
        boolean found = false;

        for(int i = 1; i < target; i++){
            if(i + (i+2) + (i+4) == target){
                System.out.print(i + " + " + (i+2) + " + " + (i+4));
                found = true;
            }

         }
         if(!found){
            System.out.println("Sorry none");
         }
     }
}

我认为需要有一个 while 循环来构建 (i+2) 增量的迭代，但我在开发正确的算法时遇到了问题。非常感谢任何帮助或提示!

最好的，奥特曼

Answer 1

假设答案等于k (k > 0)。然后对于一些奇怪的 i 我们可以写: i + (i + 2) + (i + 4) + ... + (i + 2k - 2) = target .可以看到这是arithmetic progression的总和，因此您可以使用众所周知的公式来计算它。应用公式我们可以得到:i = target/k - k + 1。

基于这个公式，我建议使用以下算法:

1. 遍历 k 的值。
2. 如果 target/k - k + 1 是正奇数，更新答案。

实现简单。

int answer = -1;
for (int k = 1;; k++) {
    int i = target / k - k + 1;
    if (i <= 0) {
        break;
    }
    // Check if calculated i, can be the start of 'odd' sequence.
    if (target % k == 0 && i % 2 == 1) {
        answer = k;
    }
}

该算法的运行时间为O(sqrt(target))。