Solution: Number factors

Grokking Dynamic Programming Patterns for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Number factors

Table of Contents

Contents are not accessible

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:

Python3

. . . .

The time complexity of the above algorithm is exponential $O(3^n)$ . The space complexity is $O(n)$ which is used to store the recursion stack.

Let's visually draw the recursion for CountWays(5) to see the overlapping subproblems:

Recursion tree for calculating Fibonacci numbers

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:

Python3

. . . .

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:

Python3

. . . .

The above solution has a time and space complexity of $O(n)$ and $O(1)$ respectively.

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

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible