CODEWITHSUNDEEP
javaalgorithmrecursiondynamic-programming
trekcampy
trekcampy

Reputation: 49

HackerRank Coding Problem : Ways to sum to N using Natural Numbers up to K with repetitions allowed

I have coded recursive solutions for this problem

int NumberOfways(int total, int K, int start, int[] memo){
    
    if (total < 0) return 0;
    if (total == 0) return 1;
    if (memo[total] != -1 ) return memo[total];
    
    memo[total]=0;
    for(int i=start;i<=K;i++){
        memo[total] += R2NumberOfways(total-i,K,i,memo);
    }

    return memo[total];
}

public static void main(String[] args)
{
    int N = 8;
    int K = 5;
    
    int[] memo = new int[N+1];
    for(int i=0; i<N+1;i++)
        memo[i] = -1;           

    System.out.println(NumberOfways(N,K,1,memo));
}

Answer for N=8, K=5 is 120, which is completely wrong. It should be 18.

But, following piece of code with global counter works and I am having difficult time understanding the difference. I am sure answer lies with the difference in recursion tree. But I am having difficulty visualizing the difference.

void NumberOfwaysWithGlobalCounter(int total, int K, int start){
    
    if (total < 0) return;
    if (total == 0) counter++;
    
    for(int i=start;i<=K;i++){
        NumberOfwaysWithGlobalCounter(total-i,K,i);
    }

    return;
}

public static void main(String[] args)
{
    int N = 8;
    int K = 5;

    counter=0;  
    NumberOfwaysWithGlobalCounter(N,K,1);
    System.out.println(counter);
}

Please help!!

Upvotes: 2

Views: 1903

Answers (1)

Dave
Dave

Reputation: 9085

Make a table where one axis represents the sum (n), and the other axis represents the max digit among all solutions (so integers from 1 to k). The cells hold the count of all solutions that sum to n and have a max digit matching their column.

Then, to go from n-1 to n, set the (n, i) cell equal to the sum of the counts all solutions in the n-1 row with max_digits <= i. This represents taking these solutions and appending an i.

Example pasted from a spreadsheet

Upvotes: 1

Related Questions