Clean recursive and iterative solutions

interview-questions
Tags: #<Tag:0x00007f241fb2eb30>

#1

First, we start with a brute force top-down recursive approach:

public class Solution {
    public int solve(int n, int s) {
        if (n == 0) {
            return s == 0 ? 1 : 0;
        }
        if (s <= 0) {
            return 0;
        }
        long count = 0;
        for (int d = 0; d < 10 && d <= s; ++d) {
            count += solve(n - 1, s - d);
        }

        return (int) (count % 1000000007L); // OJ won't accept the solution without modulo operation
    }
}

The runtime of the above solution is O(2^n) with O(n) space (consumed by recursive stack) but we can improve with memoization.

import java.util.Arrays;

public class Solution {
    public int solve(int n, int s) {
        long[][] memo = new long[n + 1][s + 1];
        for (int i = 0; i < memo.length; ++i) {
            Arrays.fill(memo[i], -1);
        }

        return (int) solve(n, s, memo);
    }

    private long solve(int n, int s, long[][] memo) {
        if (n == 0) {
            return s == 0 ? 1L : 0L;
        }
        if (s <= 0) {
            return 0L;
        }
        if (memo[n][s] != -1L) {
            return memo[n][s];
        }

        long count = 0;
        for (int d = 0; d < 10 && d <= s; ++d) {
            count += solve(n - 1, s - d, memo);
        }

        return memo[n][s] = count % 1000000007L;
    }
}

The runtime of the above solution is O(n * s) with O(n * s) extra space. Now we can turn the top-down recursive approach into bottom-up iterative:

public class Solution {
    public int solve(int n, int s) {
        long[][] dp = new long[n + 1][s + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= s; ++j) {
                long count = 0;
                for (int d = 0; d < 10 && d <= j; ++d) {
                    count += dp[i - 1][j - d];
                }
                dp[i][j] = count % 1000000007L; // interviewbit won't accept it without modulo operation
            }
        }

        return (int) dp[n][s];
    }
}

#2

How are you handling the scenario where first digit cannot be zero?


#3

Probably he is doing it when he does “++d” and not “d++” in the loop. Skips the d=0;


#4

in the recursive solution with memoisation (I didnt understand the iterative yet), it is a top down approach, so in each for loop we are subtracting d value from current sum, this indicates them to be digits from the right.
The case when we get 0 in first digit, would mean that current sum is 0, for this the case:
if (s<=0) return 0
this includes 0 also therefore we return 0, so it isnt counted


#5

There are few improvement which I would like to suggest. First you can just use dp[2][S+1] space as you are only usign i-1th row only. Second, There is no need to iterate 10 times again and again you can add dp[i-1][j] to dp[i][j-1] and subtract dp[i-1][j-10].
Something like this…
int Solution::solve(int N, int S) {
int mod = 1000000007;
if(N == 0)
return 0;
if(S == 0)
return 0;
if(N==1 && S<10)
return 1;
int F[2][S+1];
int p = 0, temp;
memset(F, 0, sizeof(F));
for(int s=1; s<=S; s++){
if(s < 10)
F[0][s] = 1;
}

for(int n=2; n<=N; n++){
    int end = 0, start = 0;
    p = 1-p;
    for(int s = 1; s<=S; s++){
        if(s-10>0)
            start++;
        end++;
        temp = F[p][s-1] - F[1-p][start];
        if(temp<0) temp = temp + mod;
        if(temp >= mod) temp -= mod;
        temp += F[1-p][end];
        if(temp >= mod) temp -= mod;
        F[p][s] = temp;
    }
}
return F[p][S];

}