数 div 从 codility。使用递归的程序中的 StackOverflowError

Question

我为 Codility 的其中一课编写了程序。它被称为计数 div。

例如。我给出数字 6、11 和 2。从 6 到 11 有 3 个数字，我们可以 divide 乘以 2，它的 6、8、10 所以方法应该 return 3.

起初我只用整数编写递归程序，但出现错误，所以我将其更改为 BigIntegers，但它根本没有帮助。它适用于小数字，但例如输入：

A = 0, B = 20000, K = 1 它给出错误：

Exception in thread "main" java.lang.WhosebugError
at java.math.MutableBigInteger.divideKnuth(Unknown Source)
at java.math.MutableBigInteger.divideKnuth(Unknown Source)
at java.math.BigInteger.remainderKnuth(Unknown Source)
at java.math.BigInteger.remainder(Unknown Source)
at java.math.BigInteger.mod(Unknown Source)
at count_div.Solution.bigIntegerSolution(Solution.java:29)
at count_div.Solution.bigIntegerSolution(Solution.java:35)

这是我的代码：

public int solution(int A, int B, int K){

    BigInteger minValue = BigInteger.valueOf(A);
    BigInteger maxValue = BigInteger.valueOf(B);
    BigInteger div = BigInteger.valueOf(K);

    finalCounter = bigIntegerSolution(minValue, maxValue, div).intValue();

    return finalCounter;
}

public BigInteger bigIntegerSolution(BigInteger minValue, BigInteger maxValue, BigInteger div){

    int comparator = minValue.compareTo(maxValue);

    if(comparator <= 0){

        BigInteger modValue = minValue.mod(div);

        if( modValue.compareTo(zero) == 0){
            divCounter = divCounter.add(one);
        }
        minValue = minValue.add(one);
        bigIntegerSolution(minValue, maxValue, div);
    }

    return divCounter;
}

有什么我可以做的，或者我的解决方案 idea 不适合这个目的吗？我知道它们是其他解决方案，但我首先想到了这个，我想知道我是否可以修复它。

Answer 1

您的 B 值越大，您的机器内存中存储的 BigIntegers 就越多。这就是为什么它适用于小值，而不适用于大值。因此，递归是解决此类问题的糟糕解决方案，因为您试图在内存中存储太多值。

Answer 2

对于这个问题，递归不是一个很好的选择，因为当您在数字中移动时，您确实没有太多的状态要存储。每次将范围增加一，深度就增加一。因此，您的堆栈溢出错误范围很大。

为此您不需要 BigInteger：导致问题的是堆栈的深度而不是变量的大小。

这是一个使用递归的解决方案：

int divisorsInRange(int min, int max, int div) {
    if (min > max)
        return 0;
    else
        return (min % div == 0 ? 1 : 0) + divisorsInRange(min + 1, max, div);
}

Non-recursive 解决方案确实更加简单高效。例如，使用 Java 8 个流：

return IntStream.range(min, max).filter(n -> n % div == 0).count();

然而，您也可以在没有任何循环或流的情况下解决这个问题。

EDIT1：错误的解决方案，但似乎是正确且优雅的。检查下面@Bopsi 提到的 min = 16, max =342, div = 17：

int countDivisors(int min, int max, int div) {
    int count = (max - min) / div;
    if (min % div == 0 || max % div == 0)
        count++;
    return count;
}

EDIT2：正确的解决方案：

int solution(int A, int B, int K) {
    const int firstDividableInRange = A % K == 0 ? A : A + (K - A % K);
    const int lastDividableInRange = B - B % K;
    const int result = (lastDividableInRange - firstDividableInRange) / K + 1;

return result;
}

Answer 3

这是 Java 中的 (100/100) 解。

class Solution {
    public int solution(int A, int B, int K) {
        int result;
        int toAdd = 0;
        int lowerBound = 0;
        int upperBound = 0;
        if (A % K == 0) {
            lowerBound = A;
            toAdd = 1;
        } else {
            lowerBound = A - A % K + K;
            if ((lowerBound - A % K) >= 0 ) {
                toAdd = 1;
            }
        }

        if (B % K == 0) {
            upperBound = B;
        } else {
            upperBound = B - B % K;
        }

        result = (upperBound - lowerBound) / K + toAdd;

        return result;
    }
}

Answer 4

您的解决方案不符合初始要求

Complexity:

expected worst-case time complexity is O(1);
expected worst-case space complexity is O(1).

一行解决

public class CountDiv {
    public int solution(int a, int b, int k) {
        return b / k - a / k + (a % k == 0 ? 1 : 0);
    }
}

Test results

Answer 5

我能够使用等差数列 (https://en.wikipedia.org/wiki/Arithmetic_progression) 解决问题。我不得不为 0 添加一个特殊情况，我无法解释，但它基于测试结果：

if (K > B)
    return A == 0 ? 1 : 0;

int min = A >= K ? A + A % K : K;
int max = B - (B % K);

// an = a1 + (n − 1) * ⋅r
return (max - min + K) / K + (A == 0 ? 1 : 0);

Answer 6

这是我的:)

public int solution(int A, int B, int K) {
    int numEl = 0;
    int first = A;
    while(numEl == 0 && first <= B) {
        if(first%K == 0) {
            numEl += 1;
        } else
           first += 1;
    }
    numEl += (B - first)/K;
    return numEl;
}

Answer 7

看代码注释看清楚图片

public int solution(int A, int B, int K) {
        int start = 0;
        int end = 0;
        int count = 0;

        start = (A % K == 0)? A : ((A / K)* K ) + K; //minimum divisible by K in the range
        end = (B % K == 0)? B : B - (B % K); // maximum divisible by K in the range

        count = ((end - start) / K) + 1; //no of divisibles by K inside the range start & end

        return count;
    }

Answer 8

这是我的解决方案。想法是，我正在寻找第一个可以在 K 上除以范围内的可除数为 ((B - first) / K) + 1 的数字。我们需要知道最大极限（B）和第一个可整除数之间的差异，并计算它们之间可以容纳多少 K 因为第一个数字不会被包括在内我们需要加一个以获得正确的结果.

class Solution {

    public int solution(int A, int B, int K) {
        if (A == B) {
            if (A % K == 0) return 1;
            else return 0;
        }
        int first = (A % K == 0) ? A : A + (K - (A % K));
        if (A != 0 && (first > B || first == 0)) return 0;

        return ((B - first) / K) + 1;
    }
}

Answer 9

简洁 ruby。这也得到 100%

def solution(a, b, k)
  b / k - (a - 1) / k
end

这个答案利用了 ruby 将自动向下舍入 2 个整数的商，返回整数结果的事实。

我们还是用原来的例子，a = 6, b = 11, k = 2

11 / 2 = 5 - 11 被 2 整除的方式总数。
(6 - 1) / 2 = 2 - 整数 < 6 被 2 整除的方式数（从总数中排除）。
5 - 2 = 3 - 从总数中减去排除的计数得到我们的结果。

这也适用于 python 的楼层划分：

def solution(A, B, K):
    return B // K - (A - 1) // K

Answer 10

我很难理解这里的一些答案，尽管它们更优雅。但是这个解决方案让我更好地推理了这个问题，也许它对你有帮助。

基本思路是移动 'A' 和 'B' 值，直到它们与 'K' 可整除性一致。也就是说，我们移动 A & B 直到 (A % K == 0) 和 (B % K == 0)。

class Solution {
    public int solution(int A, int B, int K) {
        // shift A up
        while (A % K != 0) {
            A++;
        }

        // shift B down
        while (B % K != 0) {
            B--;
        }

        return (B - A) / K + 1;
    }
}

它也可以在没有 while 循环的情况下完成，只需将 A 递增 mod 量，将 B 递减 K-mod 量。

数 div 从 codility。使用递归的程序中的 StackOverflowError

Count div from codility. StackOverflowError in program using recursion

java

stack-overflow

recursion