Count div from codility. StackOverflowError in program using recursion

Question

I wrote program for one of lessons from Codility. Its called count div.

For example. I give number 6, 11 and 2. There are 3 numbers from 6 to 11 that we can divide by 2, its 6, 8, 10 so method should return 3.

At first I made program with recursion with only ints but I got error so I changed it to BigIntegers, but it doesnt help at all. It's working good for small numbers but with for example input:

A = 0, B = 20000, K = 1 it gives errors:

Exception in thread "main" java.lang.StackOverflowError
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)

Here's my code:

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;
}

Is there anything I can do or my solution idea is just bad for this purpose? I know that they are other solutions but I first came up with this and I would like to know if I can fix it.

Answer 1

Recursion is not a great choice for this problem because you really don't have a lot of state to store as you move through the numbers. Each time you increase the range by one you increase the depth by one. Hence your stack overflow errors for a large range.

You don't need BigInteger for this: it's the depth of the stack not the size of the variables that's causing the issue.

Here is a solution using recursion:

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 solutions are really much simpler and more efficient. For example, using Java 8 streams:

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

However you can also solve this without any loops or streams.

EDIT1: Wrong solution, though seems to be correct and elegant. Check min = 16, max =342, div = 17 mentioned by @Bopsi below:

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

EDIT2: Correct solution:

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;
}