Number Factors (Count Ways to Express N as a Sum of 1, 3, and 4)

• Recurrence – dp[n] = dp[n-1] + dp[n-3] + dp[n-4], summing the ways for each valid last factor.
• Base case – dp[0] = 1, the single empty sum that reaches zero; dp[i] = 0 for negative i.
• Ordered sums – 1+3 and 3+1 are counted separately, which is the natural result of summing predecessor counts.
• Bottom-up – fill dp[0..N] left to right; only the last 4 values matter, so rolling variables give O(1) space.
• Complexity – O(n) time, O(1) space with rolling variables.

What is the problem?

Given a positive integer N, count the number of distinct ordered ways to express N as a sum using only the values 1, 3, and 4. Order matters: 1+3 and 3+1 are two different ways.

How does the recurrence work?

The last factor in any valid sum is either 1, 3, or 4. If the last factor is 1, the remaining sum is N-1. If 3, the remaining is N-3. If 4, the remaining is N-4. So:

dp[n] = dp[n-1] + dp[n-3] + dp[n-4]

with dp[0] = 1 (one way to reach zero: use no factors) and dp[i] = 0 for negative i.

How do you implement it?

package com.bank.service;

public class LoyaltyWaysCounter {

    public static int countWays(int n) {
        if (n < 0) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 1; // base case: empty sum
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1]; // last factor = 1
            if (i >= 3) dp[i] += dp[i - 3]; // last factor = 3
            if (i >= 4) dp[i] += dp[i - 4]; // last factor = 4
        }
        return dp[n];
    }

    public static void main(String[] args) {
        // Loyalty target at National Bank of India
        for (int n = 0; n <= 6; n++) {
            System.out.println("Ways to reach " + n + ": " + countWays(n));
        }
    }
}

Ways to reach 0: 1
Ways to reach 1: 1
Ways to reach 2: 1
Ways to reach 3: 2
Ways to reach 4: 4
Ways to reach 5: 6
Ways to reach 6: 9

How do you verify N=4 has 4 ways?

The four ordered sums for N=4 are: {1,1,1,1}, {1,3}, {3,1}, {4}. Check: dp[3] + dp[1] + dp[0] = 2 + 1 + 1 = 4.

How do you optimize space with rolling variables?

Only the last 4 values are needed at any time.

public static int countWaysOptimized(int n) {
    if (n == 0) return 1;
    int[] window = new int[4]; // indices 0..3 for dp[i-4]..dp[i-1]
    window[3] = 1; // dp[0] = 1
    for (int i = 1; i <= n; i++) {
        int ways = window[3]; // dp[i-1]
        if (i >= 3) ways += window[1]; // dp[i-3]
        if (i >= 4) ways += window[0]; // dp[i-4]
        // Shift window
        window[0] = window[1];
        window[1] = window[2];
        window[2] = window[3];
        window[3] = ways;
    }
    return window[3];
}

How is this different from the Fibonacci pattern?

Fibonacci uses two offsets (n-1 and n-2). Number Factors uses three offsets (n-1, n-3, n-4). The idea is the same: the count at position n is the sum of counts at the reachable predecessors. This generalizes to any set of step sizes.

| Feature | Fibonacci | Number Factors |
|---|---|---|
| Offsets | n-1, n-2 | n-1, n-3, n-4 |
| Rolling variables | 2 | 4 |
| Base case | dp[0]=0, dp[1]=1 | dp[0]=1 |
| Ordered? | n/a | yes, order matters |

What are edge cases?

• N=0: 1 way (the empty sum).
• N=1: 1 way ({1}).
• N=2: 1 way ({1,1}).
• Negative N: 0 ways.

What are common mistakes?

// Wrong: base case dp[0] = 0
dp[0] = 0; // makes every dp[i] = 0!

// Correct: dp[0] = 1
dp[0] = 1; // the empty sum is one valid way

What should a senior engineer know?

If the problem asked for unordered combinations (1+3 and 3+1 count as one), the approach changes to a coin-change style DP where you iterate over factors in an outer loop and amounts in an inner loop. The ordered variant is simpler because it just sums predecessor counts.

What are common interview follow-up questions?

• How would you list all the actual sequences, not just count them?
• What if the factors were {2, 3, 7} instead of {1, 3, 4}?
• How would you handle very large N where the count overflows an int?