The Number of Ways to Make the Sum
VisaThe 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)
{
}
}go
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
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
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question