 # Clean recursive and iterative solutions

Tags: #<Tag:0x00007f241fb2eb30>

#1

``````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 = 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[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[S+1];
int p = 0, temp;
memset(F, 0, sizeof(F));
for(int s=1; s<=S; s++){
if(s < 10)
F[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];
``````

}