Coding

The Number of Ways to Make the Sum

Asked at

Visa

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an infinite number of coins with values 1, 2, and 6, and only 2 coins with value 4 and an integer n, return the number of ways to make the sum n using the available coins.

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

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

Input: n = 10 Output: 16 Explanation: Some valid combinations include: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2, 2, 2, 2, 2] [6, 2, 2] [4, 4, 2] (Valid since 4 can be used at most twice) [6, 4] [2, 2, 2, 2, 1, 1] [1, 1, 1, 1, 6]

Input: n = 7

1 ≤ n ≤ 105

cpp

class Solution {
public:
    int numberOfWays(int n) {
        
    }
};

java

class Solution {
    public int numberOfWays(int n) {
        
    }
}

python

class Solution:
    def numberOfWays(self, n):

javascript

class Solution {
    numberOfWays(n) {
  
    }
}

csharp

public class Solution
{
    public int NumberOfWays(int n)
    {
        
    }
}

func numberOfWays(n int) int {
	// Your code goes here
}

Stuck? Show a way to structure it+

01Count unlimited combinations for denominations 1, 2, and 6.
02Handle the bounded denomination 4 with usage 0, 1, or 2.
03Accumulate states modulo the given modulus.
04Ensure denomination order prevents permutation overcounting.

Reference answer

Use a combinations DP where dp[s] counts ways to make sum s, initialized with dp[0]=1. Process unlimited coins 1, 2, and 6 with forward loops. For the two available 4-coins, either process two separate 0/1 updates in descending sum order, or combine contributions for using zero, one, or two fours. Keep every update modulo 1e9+7. This is O(n) time and O(n) space for fixed denominations. Iterating sums before coin types would count different orders of the same coins as separate ways. In an interview, make the invariant explicit before writing code, trace a boundary example that breaks a tempting shortcut, state what each stored value represents, and explain why every update preserves correctness. This verification step also surfaces empty-input, duplicate-value, and numeric-limit cases.

Then expect these follow-ups

How would arbitrary bounded coin counts change the DP?
Tests: bounded knapsack
Can you derive a recurrence for this fixed set?
Tests: recurrences

Hiring now

Visa has 638 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer Intern
GB - London, United Kingdom
Sr. Software Engineer (3+ yrs, DevOps, Cloud, Coding, Infra)
IN - Bengaluru, India
Sr Software Engineer (3-5 yrs of exp - Full stack development, Java, React, Gen AI)
IN - Bengaluru, India

Or practice this question first

Next question