interviewbit-solutions/n-digit-numbers-with-digit-sum-s-.cpp at master · babu-thomas/interviewbit-solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#define MOD 1000000007

int rec(int num_digits, int sum, vector<vector<int>>& seen) {
    if(seen[num_digits][sum] != -1) {
        return seen[num_digits][sum];
    }

    if(num_digits == 1) {
        if(sum > 9) {
            seen[num_digits][sum] = 0;
            return 0;
        }

        seen[num_digits][sum] = 1;
        return 1;
    }

    if(sum == 0) {
        seen[num_digits][sum] = 1;
        return 1;
    }

    long long result = 0;
    for(int i = 0; i <= 9 && i <= sum; i++) {
        result = (result + rec(num_digits - 1, sum - i, seen)) % MOD;
    }

    seen[num_digits][sum] = result;
    return result;
}

// Time - O(A * B), Space - O(A * B)
int Solution::solve(int A, int B) {
    int num_digits = A;
    int sum = B;

    if(num_digits == 0) {
        return 0;
    }

    if(num_digits == 1) {
        if(sum > 9 || sum == 0) {
            return 0;
        }

        return 1;
    }

    vector<vector<int>> seen(num_digits + 1, vector<int>(sum + 1, -1));

    long long result = 0;
    for(int i = 1; i <= 9 && i <= sum; i++) {
        result = (result + rec(num_digits - 1, sum - i, seen)) % MOD;
    }

    return result;
}


// Shorter version

#define MOD 1000000007

int rec(int num_digits, int sum, vector<vector<int>>& seen) {
    if(sum < 0) {
        return 0;
    }

    if(num_digits == 0 && sum == 0) {
        return 1;
    }

    if(num_digits == 0) {
        return 0;
    }

    if(seen[num_digits][sum] != -1) {
        return seen[num_digits][sum];
    }

    int result = 0;
    for(int i = 0; i < 10; i++) {
        result += rec(num_digits - 1, sum - i, seen);
        result %= MOD;
    }

    seen[num_digits][sum] = result;

    return result;
}

// Time - O(A * B), Space - O(A * B)
int Solution::solve(int A, int B) {
    int num_digits = A;
    int sum = B;

    int result = 0;
    vector<vector<int>> seen(num_digits + 1, vector<int>(sum + 1, -1));

    for(int i = 1; i < 10; i++) {
        result += rec(num_digits - 1, sum - i, seen);
        result %= MOD;
    }

    return result;
}