Count div from codility. StackOverflowError in program using recursion

codility problems
codility r
codility test in python
codility challenges
codility test ios
codility spark
codility test questions and answers c# pdf
codility react test

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.

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

Solution to Count-Div by codility – Code Says, Because the code is really simple. As long as you get the idea with math, coding is completely not a challenge. Reply. Rachel  I'm using Iterator to loop the keys, and using hasNext() and next() to ensure that I should only be able to access specific object keys. I started testing with a simple JSONObject of:

Your solution is out of initial requirements

Complexity:

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

One line solution

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

Test results

Recursion in Java, Using recursive algorithm, certain problems can be solved quite easily. In the recursive program, the solution to the base case is provided and the solution of is exhausted by these functions on the stack, it will cause a stack overflow error. Here is the source code of the C Program Count Occurrence of Element in Linked List using Recursion. The C Program is successfully compiled and run on a Linux system. The program output is also shown below.

The bigger your B value, the more BigIntegers will be stored in your machine memory. That is why, it works fine with small values, and does not work with big ones. So, recursion is a bad solution to solve this kind of a problem, because you are trying to store too many values in memory.

codility by jsuchal, Count div from codility. StackOverflowError in program using recursion; Finding the missing integer (Codility tests); Tape-Equilibrium Codility  Codility is a software platform that helps technical recruiters run remote interviews and hire strong engineers. Explore our platform by requesting a demo today.

Here is (100/100) solution in Java.

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

java, Minél nagyobb a B érték, annál BigIntegers lesznek tárolva a készülék memóriájában. Ezért van az, hogy jól működik a kis értékek és nem működik nagyok. Chesstrian March 21, 2020 at 9:23 am on Solution to Count-Div by codility Given any two natural numbers, the number of divisors is exactly the natural division between them: x // y # In python In order to

I was able to solve the problem using arithmetic progression (https://en.wikipedia.org/wiki/Arithmetic_progression). I've had to add a special case for 0, which I can't explain but it was based on the test results:

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

java, StackOverflowError at java.math. int divisorsInRange(int min, int max, int div) { if (min > max) return 0; else return (min % div == 0 ? return IntStream.range(min, max).filter(n -> n % div == 0).count(); Folgen Sie den Code Kommentare klares Bild zu erhalten By using our services, you agree to our use of cookies. Count in factors You are encouraged to solve this task according to the task description, using any language you may know.

Conteaza div de codilitate. StackOverflowError în program utilizând , Soluțiile non-recursive sunt într-adevăr mult mai simple și mai eficiente. int countDivisors(int min, int max, int div) { int count = (max - min)/div; if (min % div  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 w

Keep Coding. java, maven, image, vim, multithreading, Open the category tree on the left to find what you need or use the search engine on Count div from codility. StackOverflowError in program using recursion. « first day (554 days earlier) ← previous day next day → last day (639 days later) »

Java Exception Handling - StackOverflowError, As with most programming languages, the StackOverflowError in Java occurs when the application performs excessively deep recursion. call self. this.count​++; increment(); } catch (StackOverflowError error) { // Get elapsed  There’s almost certainly going to be better techniques for this depending on your recursive routine and what it does, but if you want something that is super generic and can almost always certainly be used then switch from stack use to heap use by

Comments
  • You want us to replace your recursive algorithm with non-recursive one. It is not always trivial problem, so you have to do it without assistance
  • I don't want you to replace my algorithm. I would like to do this exercise with recursive if it is possible and I'm asking if there is something in my method that causes stackoverflow error. I wrote at the end of my post that I know that they are other solutions for this problem but I would like to know why my solution doesnt work and/or why this solution is bad.
  • Can I ask why you need recursion for this? The problem you're hitting (which I think you've already identified) is that for every call to bigIntegerSolution, you're adding another item to the stack, and 20,000 entries is too many. You could increase the stack size (Google will tell you how), but you'll always hit a limit. Why is recursion better here than just a normal for loop, from minValue to maxValue?
  • None of the solutions meet complexity requirements for this exercise: Complexity: expected worst-case time complexity is O(1); expected worst-case space complexity is O(1).
  • fails with min = 16, max 342, and div = 17
  • Can you please explain why did you write this solution? Let say i am asking from the perspective of interviewer.
  • It is prefix-sum @ZeeshanShabbir, B is the upper bound, and A is the lower bound. first, you count all the divisor available from 1 to upper bound by B/K then you count all the divisor available from 1 to lower bound by A/K Then you use B/K - A/K, you will get all the divisor from A to B But wait, what if A divisible by K, then you will count it 2 times (from A and from B) then you need to check it to make sure it is only counted once.