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

Contents are not accessible

Contents are not accessible

Contents are not accessible

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
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
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
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
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

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible