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 10⁹ + 7.

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

Input & Output

Example 1 — Small Sum

$ Input: n = 8

› Output: 21

💡 Note: Multiple ways to make 8: using coins {1,1,6}, {2,2,2,2}, {1,1,2,4}, {4,4}, etc. Total of 21 different combinations.

Example 2 — Minimum Case

$ Input: n = 1

› Output: 1

💡 Note: Only one way to make sum 1: use a single coin of value 1.

Example 3 — Medium Sum

$ Input: n = 4

› Output: 5

💡 Note: Ways to make 4: {1,1,1,1}, {1,1,2}, {2,2}, {4}. Note we can use one coin-4 from our limited supply.

Constraints

1 ≤ n ≤ 10⁴
Answer modulo 10⁹ + 7

Visualization

Tap to expand

Asked in

G Google 25 a Amazon 20 M Microsoft 15

This is a coin change variation with mixed constraints. The key insight is to track the number of limited coin-4s used as part of the DP state. Best approach uses 2D DP with state (sum, coin4_count). Time: O(n), Space: O(n).

Common Approaches

✓ Bottom-Up 2D DP

⏱️ Time: O(n) Space: O(n)

Create a 2D DP table where dp[i][j] represents number of ways to make sum i using j coins of value 4. Fill table bottom-up by considering each coin type systematically.

Memoization (Top-Down DP)

⏱️ Time: O(n) Space: O(n)

Use the same recursive approach but store results in a memo table to avoid recalculating the same subproblems. Key insight is that state depends on remaining sum and number of coin-4s used.

Recursive Brute Force

⏱️ Time: O(3ⁿ) Space: O(n)

For each position, try using each available coin type and recursively solve for the remaining sum. Check all combinations including 0, 1, or 2 coins of value 4.

Bottom-Up 2D DP — Algorithm Steps

Initialize DP table dp[sum][coin4_count]
Fill base cases (sum = 0)
For each sum and coin4 count, try adding coins 1, 2, 6
Handle coin 4 transitions separately

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set dp[0][0] = 1 (base case)

Fill Table

For each state, add coin transitions

Combine

Sum dp[n][0] + dp[n][1] + dp[n][2]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

const int MOD = 1000000007;

int solution(int n) {
    // dp[i][j] = ways to make sum i using j coins of value 4
    long long dp[n + 1][3];
    
    // Initialize
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < 3; j++) {
            dp[i][j] = 0;
        }
    }
    dp[0][0] = 1; // Base case
    
    // Process each sum from 1 to n
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 3; j++) { // for each number of coin 4s used so far
            // Add unlimited coins (1, 2, 6)
            if (i >= 1) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
            }
            if (i >= 2) {
                dp[i][j] = (dp[i][j] + dp[i - 2][j]) % MOD;
            }
            if (i >= 6) {
                dp[i][j] = (dp[i][j] + dp[i - 6][j]) % MOD;
            }
            
            // Add limited coin 4 (if we haven't used 2 already)
            if (i >= 4 && j > 0) {
                dp[i][j] = (dp[i][j] + dp[i - 4][j - 1]) % MOD;
            }
        }
    }
    
    return (dp[n][0] + dp[n][1] + dp[n][2]) % MOD;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Iterate through all states (sum, coin4_count), each state processes 3-4 transitions

✓ Linear Growth

Space Complexity

O(n)

DP table of size 3n (n sums × 3 possible coin4 counts)

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

The Number of Ways to Make the Sum - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bottom-Up 2D DP — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler