Solution Number factors
Problem Statement
Given a number 'n', implement a method to count how many possible ways there are to express 'n' as the sum of 1, 3, or 4.
Example 1:
n : 4
Number of ways = 4
Explanation: Following are the four ways we can express 'n' : {1,1,1,1}, {1,3}, {3,1}, {4}
Example 2:
n : 5
Number of ways = 6
Explanation: Following are the six ways we can express 'n' : {1,1,1,1,1}, {1,1,3}, {1,3,1}, {3,1,1},
{1,4}, {4,1}
Let's first start with a recursive brute-force solution.
Basic Solution
For every number 'i', we have three option: subtract either 1, 3, or 4 from 'i' and recursively process the remaining number. So our algorithm will look like:
class Solution {
public int countWays(int n) {
if (n == 0) return 1; // base case, we don't need to subtract any thing, so there is only one way
if (n == 1) return 1; // we can subtract 1 to be left with zero, and that is the only way
if (n == 2) return 1; // we can subtract 1 twice to get zero and that is the only way
if (n == 3) return 2; // '3' can be expressed as {1,1,1}, {3}
// if we subtract 1, we are left with 'n-1'
int subtract1 = countWays(n - 1);
// if we subtract 3, we are left with 'n-3'
int subtract3 = countWays(n - 3);
// if we subtract 4, we are left with 'n-4'
int subtract4 = countWays(n - 4);
return subtract1 + subtract3 + subtract4;
}
public static void main(String[] args) {
Solution en = new Solution();
System.out.println(en.countWays(4));
System.out.println(en.countWays(5));
System.out.println(en.countWays(6));
}
}
The time complexity of the above algorithm is exponential
Let's visually draw the recursion for CountWays(5) to see the overlapping subproblems:
We can clearly see the overlapping subproblem pattern: CountWays(3), CountWays(2) and CountWays(1) have been called twice. We can optimize this using memoization to store the results for subproblems.
Top-down Dynamic Programming with Memoization
We can use an array to store the already solved subproblems. Here is the code:
class Solution {
public int countWays(int n) {
int dp[] = new int[n + 1];
return countWaysRecursive(dp, n);
}
public int countWaysRecursive(int[] dp, int n) {
if (n == 0) return 1; // base case, we don't need to subtract any thing, so there is only one way
if (n == 1) return 1; // we can take subtract 1 to be left with zero, and that is the only way
if (n == 2) return 1; // we can subtract 1 twice to get zero and that is the only way
if (n == 3) return 2; // '3' can be expressed as {1,1,1}, {3}
if (dp[n] == 0) {
// if we subtract 1, we are left with 'n-1'
int subtract1 = countWaysRecursive(dp, n - 1);
// if we subtract 3, we are left with 'n-3'
int subtract3 = countWaysRecursive(dp, n - 3);
// if we subtract 4, we are left with 'n-4'
int subtract4 = countWaysRecursive(dp, n - 4);
dp[n] = subtract1 + subtract3 + subtract4;
}
return dp[n];
}
public static void main(String[] args) {
Solution en = new Solution();
System.out.println(en.countWays(4));
System.out.println(en.countWays(5));
System.out.println(en.countWays(6));
}
}
Bottom-up Dynamic Programming
Let's try to populate our dp[] array from the above solution, working in a bottom-up fashion. As we saw in the above code, every CountWaysRecursive(n) is the sum of the three counts. We can use this fact to populate our array.
Code
Here is the code for our bottom-up dynamic programming approach:
class Solution {
public int countWays(int n) {
// bottom up
int n0 = 1, n1 = 1, n2 = 1, n3 = 2;
for(int i = 4; i <= n; i++){
int temp = n0 + n1 + n3;
n0 = n1;
n1 = n2;
n2 = n3;
n3 = temp;
}
return n3;
}
public static void main(String[] args) {
Solution en = new Solution();
System.out.println(en.countWays(4));
System.out.println(en.countWays(5));
System.out.println(en.countWays(6));
}
}
The above solution has a time and space complexity of
Fibonacci number pattern
We can clearly see that this problem follows the Fibonacci number pattern. However, every number in a Fibonacci series is the sum of the previous two numbers, whereas in this problem every count is a sum of previous three numbers: previous-1, previous-3, and previous-4. Here is the recursive formula for this problem:
CountWays(n) = CountWays(n-1) + CountWays(n-3) + CountWays(n-4), for n >= 4
🤖 Don't fully get this? Learn it with Claude
Stuck on Solution Number factors? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
Progressively stronger hints — you still solve it.
I'm working on the problem **Solution Number factors** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
See the technique, not just code.
Explain the optimal approach to **Solution Number factors** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Catch bugs, edge cases, sub-optimality.
I'll paste my solution to **Solution Number factors**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Lock in recognition with look-alikes.
Give me 2 problems that use the SAME underlying pattern as **Solution Number factors**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.