Skip to content

3183. The Number of Ways to Make the Sum 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int numberOfWays(int n) {
    constexpr int kMod = 1'000'000'007;
    // dp[i] := the number of ways to make the sum of i using coins 1, 2, and 6
    vector<int> dp(n + 1);
    dp[0] = 1;

    for (const int coin : {1, 2, 6})
      for (int i = coin; i <= n; ++i)
        dp[i] = (dp[i] + dp[i - coin]) % kMod;

    int ans = dp[n];
    if (n - 4 >= 0)
      ans = (ans + dp[n - 4]) % kMod;
    if (n - 8 >= 0)
      ans = (ans + dp[n - 8]) % kMod;
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int numberOfWays(int n) {
    final int kMod = 1_000_000_007;
    // dp[i] := the number of ways to make the sum of i using coins 1, 2, and 6
    int[] dp = new int[n + 1];
    dp[0] = 1;

    for (final int coin : new int[] {1, 2, 6})
      for (int i = coin; i <= n; ++i)
        dp[i] = (dp[i] + dp[i - coin]) % kMod;

    int ans = dp[n];
    if (n - 4 >= 0)
      ans = (ans + dp[n - 4]) % kMod;
    if (n - 8 >= 0)
      ans = (ans + dp[n - 8]) % kMod;
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def numberOfWays(self, n: int) -> int:
    kMod = 1_000_000_007
    # dp[i] := the number of ways to make the sum of i using coins 1, 2, and 6
    dp = [1] + [0] * n

    for coin in (1, 2, 6):
      for i in range(coin, n + 1):
        dp[i] = (dp[i] + dp[i - coin]) % kMod

    ans = dp[n]
    if n - 4 >= 0:
      ans = (ans + dp[n - 4]) % kMod
    if n - 8 >= 0:
      ans = (ans + dp[n - 8]) % kMod
    return ans