CODEWITHSUNDEEP
javarecursioncachingbinomial-coefficients
bobacrack
bobacrack

Reputation: 9

Java Binomial recursion using cache

I ran into a little problem having to solve the binomial coefficient using a 1d Integer array as a cache. this is my code thus far:

static public int computeCached(int n, int k) throws ArithmeticException, IllegalArgumentException {
        if(n < 0 || k < 0 || n < k)
            throw new IllegalArgumentException("Illegal");

        int cache[] = new int[n + 1];
        return computeCached(n, k, cache);
    }

    
    static int computeCached(int n, int k, int []cache) throws ArithmeticException {
        if(k == 0 || n == k)
            return 1;
        if(cache[n] != 0)
            return cache[n];
        cache[n] = Math.addExact(computeCached(n-1, k, cache), computeCached(n-1,k-1, cache));
        return cache[n];
    }

It's supposed to store the calculated value and then add the next value for the next iteration on top. somehow it doesnt save the right value in the cache and i cant seem to find the problem. thanks :)

Upvotes: 0

Views: 154

Answers (1)

MDK
MDK

Reputation: 499

As discussed in the comments, the problem is that your mapping is ambiguous. You store all (n,k) pairs with different values for k in the same array entry. As a solution you will have to calculate a unique index for each combination of n and k, e.g. ((n*(n+1))/2)+k, which would "flatten" the triangle using the sum formula. Simpler mappings like n*k + k would also work, but required a larger cache than actually needed, with some arry entries never getting used.

Upvotes: 0

Related Questions