The Number of Ways to Make the Sum

Problem

You have an infinite number of coins with values 1, 2, and 6, and only 2 coins with value 4.

Given an integer n, return the number of ways to make the sum of n with the coins you have.

Since the answer may be very large, return it modulo 109 + 7.

Note that the order of the coins doesn’t matter and [2, 2, 3] is the same as [2, 3, 2].

Examples

Example 1:

1
2
3
4


Input: n = 4
Output: 4
Explanation:
Here are the four combinations: `[1, 1, 1, 1]`, `[1, 1, 2]`, `[2, 2]`, `[4]`.

Example 2:

1
2
3
4
5


Input: n = 12
Output: 22
Explanation:
Note that `[4, 4, 4]` is **not** a valid combination since we cannot use 4
three times.

Example 3:

1
2
3
4
5


Input: n = 5
Output: 4
Explanation:
Here are the four combinations: `[1, 1, 1, 1, 1]`, `[1, 1, 1, 2]`, `[1, 2,
2]`, `[1, 4]`.

Constraints:

1 <= n <= 10^5

Solution

Method 1 - Bounded Knapsack for Coin 4

We use dynamic programming. For coins 1, 2, 6 (infinite), and 4 (at most 2), we first compute ways without 4, then add ways using 4 once and twice.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include <vector>
using namespace std;
class Solution {
public:
    int waysToReachSum(int n) {
        const int MOD = 1e9+7;
        vector<int> dp(n+1);
        dp[0] = 1;
        int coins[] = {1,2,6};
        for (int c : coins)
            for (int i = c; i <= n; ++i)
                dp[i] = (dp[i] + dp[i-c]) % MOD;
        vector<int> res = dp;
        for (int i = 4; i <= n; ++i)
            res[i] = (res[i] + dp[i-4]) % MOD;
        for (int i = 8; i <= n; ++i)
            res[i] = (res[i] + dp[i-8]) % MOD;
        return res[n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
    public int waysToReachSum(int n) {
        int MOD = 1000000007;
        int[] dp = new int[n+1];
        dp[0] = 1;
        int[] coins = {1,2,6};
        for (int c : coins)
            for (int i = c; i <= n; ++i)
                dp[i] = (dp[i] + dp[i-c]) % MOD;
        int[] res = dp.clone();
        for (int i = 4; i <= n; ++i)
            res[i] = (res[i] + dp[i-4]) % MOD;
        for (int i = 8; i <= n; ++i)
            res[i] = (res[i] + dp[i-8]) % MOD;
        return res[n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def waysToReachSum(self, n: int) -> int:
        MOD = 10**9 + 7
        dp = [0] * (n+1)
        dp[0] = 1
        for c in [1,2,6]:
            for i in range(c, n+1):
                dp[i] = (dp[i] + dp[i-c]) % MOD
        res = dp[:]
        for i in range(4, n+1):
            res[i] = (res[i] + dp[i-4]) % MOD
        for i in range(8, n+1):
            res[i] = (res[i] + dp[i-8]) % MOD
        return res[n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


impl Solution {
    pub fn ways_to_reach_sum(n: i32) -> i32 {
        let n = n as usize;
        let m = 1_000_000_007;
        let mut dp = vec![0; n+1];
        dp[0] = 1;
        for &c in &[1,2,6] {
            for i in c..=n {
                dp[i] = (dp[i] + dp[i-c]) % m;
            }
        }
        let mut res = dp.clone();
        for i in 4..=n {
            res[i] = (res[i] + dp[i-4]) % m;
        }
        for i in 8..=n {
            res[i] = (res[i] + dp[i-8]) % m;
        }
        res[n]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


function waysToReachSum(n: number): number {
    const MOD = 1e9+7;
    const dp = new Array(n+1).fill(0);
    dp[0] = 1;
    for (const c of [1,2,6]) {
        for (let i = c; i <= n; ++i) {
            dp[i] = (dp[i] + dp[i-c]) % MOD;
        }
    }
    const res = dp.slice();
    for (let i = 4; i <= n; ++i) res[i] = (res[i] + dp[i-4]) % MOD;
    for (let i = 8; i <= n; ++i) res[i] = (res[i] + dp[i-8]) % MOD;
    return res[n];
}

Complexity

⏰ Time complexity: O(n)
🧺 Space complexity: O(n)

Problem#

Examples#

Solution#

Method 1 - Bounded Knapsack for Coin 4#

Code#

Complexity#