Number Factor Problem

Given N, count the number of ways to express N as sum of 1,3 and 4.

Example 1
-----------
n: 4
num of ways: 4
Explanation: There are four ways to express 'n': {4}, {1,3}, {3,1}, {1,1,1,1}

Example 2
-----------
n: 5
num of ways: 6
Explanation: There are six ways to express 'n': {4,1}, {1,4}, {3,1,1}, {1,3,1}, {1,1,3}, {1,1,1,1,1}

Solution

This problem can be solved by applying Divide and Conquer algorithm techniques. Firstly, let’s try to break the problem into smaller subproblems. Since we are given 3 numbers, {1,3,4}, let’s try to find the complements of those numbers and also the number of ways to form those complements. We will use the example where N = 5:

n = 5

1 | + 4 = {1,1,1,1}, {1,3}, {3,1}, {4} = 4 ways
3 | + 2 = {1,1} = 1 way
4 | + 1 = {1} = 1 way

num of ways: 4 + 1 + 1 = 6

By solving the subproblems, we arrive at the final result by getting the sum of all the answers to the subproblems.

Code Algorithm

function numWays(n: number): number {
  if (n === 0 || n === 1 || n === 2) return 1;
  if (n === 3) return 2;

  const comp1 = numWays(n - 1);
  const comp2 = numWays(n - 3);
  const comp3 = numWays(n - 4);

  return comp1 + comp2 + comp3;
}

Optimisation

Let’s look at the an example of the recursion tree using N = 8 for a larger recursive tree and see if we can optimise this solution.

                  numWays(8)
      /               |                   \
numWays(7)        numWays(5)        numWays(4)
  |                   |                   |
  |-numWays(6)       |-numWays(4)       |-numWays(3)
  |-numWays(4)       |-numWays(2)       |-numWays(1)
  |-numWays(3)       |-numWays(1)       |-numWays(0)

We are computing a new of the subproblems more than once such as numWays(4). We can then apply Dynamic Programming to optimise the solution.

Top Down Approach

We will start off by applying Top Down Approach (also known as Memoization).

type HashTable = {
  [x: number]: number;
};

const dp: HashTable = {};

function numWays(n: number): number {
  if (n === 0 || n === 1 || n === 2) return 1;
  if (n === 3) return 2;

  if (!(n in dp)) {
    const comp1 = numWays(n - 1);
    const comp2 = numWays(n - 3);
    const comp3 = numWays(n - 4);

    dp[n] = comp1 + comp2 + comp3;
  }

  return dp[n];
}

Bottom Up Approach

We can now then apply some reverse engineer to use the Bottom Up Approach (also known as Tabulation). Let’s visualise how dp is filled using Top Down Approach.

We can then now reverse the process. Let’s visualize how Bottom Up Approach works here.

type HashTable = {
  [x: number]: number;
};

function numWays(n: number): number {
  const dp: HashTable = {
    0: 1,
    1: 1,
    2: 1,
    3: 2,
  };

  for (let i = 4; i < n + 1; ++i) {
    dp[i] = dp[i - 1] + dp[i - 3] + dp[i - 4];
  }

  return dp[n];
}