Given N, count the number of ways to express N as sum of 1, 3 and 4.
Examples:
Input : N = 4
Output : 4
Explanation: 1+1+1+1
1+3
3+1
4
Input : N = 5
Output : 6
Explanation: 1 + 1 + 1 + 1 + 1
1 + 4
4 + 1
1 + 1 + 3
1 + 3 + 1
3 + 1 + 1
Approach : Divide the problem into sub-problems for solving it. Let DP[n] be the number of ways to write N as the sum of 1, 3, and 4. Consider one possible solution with n = x1 + x2 + x3 + … xn. If the last number is 1, then sum of the remaining numbers is n-1. So the number that ends with 1 is equal to DP[n-1]. Taking other cases into account where the last number is 3 and 4. The final recurrence would be:
DPn = DPn-1 + DPn-3 + DPn-4
Base case : DP[0] = DP[1] = DP[2] = 1 and DP[3] = 2
C++
// C++ program to illustrate the number of// ways to represent N as sum of 1, 3 and 4.#include <bits/stdc++.h>using namespace std;// function to count the number of// ways to represent n as sum of 1, 3 and 4int countWays(int n){ int DP[n + 1]; // base cases DP[0] = DP[1] = DP[2] = 1; DP[3] = 2; // iterate for all values from 4 to n for (int i = 4; i <= n; i++) DP[i] = DP[i - 1] + DP[i - 3] + DP[i - 4]; return DP[n];}// driver codeint main(){ int n = 10; cout << countWays(n); return 0;} |
Java
// Java program to illustrate // the number of ways to represent // N as sum of 1, 3 and 4.class GFG { // Function to count the // number of ways to represent // n as sum of 1, 3 and 4 static int countWays(int n) { int DP[] = new int[n + 1]; // base cases DP[0] = DP[1] = DP[2] = 1; DP[3] = 2; // iterate for all values from 4 to n for (int i = 4; i <= n; i++) DP[i] = DP[i - 1] + DP[i - 3] + DP[i - 4]; return DP[n]; } // driver code public static void main(String[] args) { int n = 10; System.out.println(countWays(n)); }}// This code is contributed // by prerna saini. |
Python3
# Python program to illustrate the number of# ways to represent N as sum of 1, 3 and 4.# Function to count the number of# ways to represent n as sum of 1, 3 and 4def countWays(n): DP = [0 for i in range(0, n + 1)] # base cases DP[0] = DP[1] = DP[2] = 1 DP[3] = 2 # Iterate for all values from 4 to n for i in range(4, n + 1): DP[i] = DP[i - 1] + DP[i - 3] + DP[i - 4] return DP[n] # Driver code n = 10print (countWays(n))# This code is contributed by Gitanjali. |
C#
// C# program to illustrate // the number of ways to represent // N as sum of 1, 3 and 4.using System;class GFG { // Function to count the // number of ways to represent // n as sum of 1, 3 and 4 static int countWays(int n) { int []DP = new int[n + 1]; // base cases DP[0] = DP[1] = DP[2] = 1; DP[3] = 2; // iterate for all values from 4 to n for (int i = 4; i <= n; i++) DP[i] = DP[i - 1] + DP[i - 3] + DP[i - 4]; return DP[n]; } // Driver code public static void Main() { int n = 10; Console.WriteLine(countWays(n)); }}// This code is contributed // by vt_m. |
PHP
<?php// PHP program to illustrate // the number of ways to // represent N as sum of // 1, 3 and 4.// function to count the // number of ways to // represent n as sum of// 1, 3 and 4function countWays($n){ $DP = array(); // base cases $DP[0] = $DP[1] = $DP[2] = 1; $DP[3] = 2; // iterate for all // values from 4 to n for ($i = 4; $i <= $n; $i++) $DP[$i] = $DP[$i - 1] + $DP[$i - 3] + $DP[$i - 4]; return $DP[$n];}// Driver Code$n = 10;echo countWays($n);// This code is contributed// by Sam007?> |
Javascript
<script>// Javascript program to illustrate// the number of ways to represent// N as sum of 1, 3 and 4.// Function to count the// number of ways to represent// n as sum of 1, 3 and 4function countWays(n){ var DP = []; DP.length = 10; DP.fill(0); // Base cases DP[0] = DP[1] = DP[2] = 1; DP[3] = 2; // Iterate for all values from 4 to n for(var i = 4; i <= n; i++) DP[i] = DP[i - 1] + DP[i - 3] + DP[i - 4]; return DP[n];}// Driver codevar n = 10;document.write(countWays(n));// This code is contributed by bunnyram19 </script> |
Output
64
Time Complexity : O(n)
Auxiliary Space : O(n)
Method – 2: Constant Space Complexity Solution (O(1) space complexity)
In the above solution we are storing all the dp states, i.e. we create n + 1 size dp array, but to calculate the particular dp[i[4] state we only need the dp[i-1], dp[i-3] and dp[i-4] states. so we can use this observation and conclude that we only store the previous 4 states to calculate the current dp[i] state.
so here we use
dp_i which store dp[i] dp_i_1 which store dp[i-1] dp_i_2 which store dp[i-2] dp_i_3 which store dp[i-3] dp_i_4 which store dp[i-4]
so in this solution we only need 5 variable so space complexity = O(5) ~= O(1)
below is the Implementation for this approach
C++
// C++ program to illustrate the number of ways to represent N as sum of 1, 3 and 4.#include <bits/stdc++.h>using namespace std;// function to count the number of ways to represent n as sum of 1, 3 and 4int countWays(int n) { int dp_i, dp_i_1, dp_i_2, dp_i_3, dp_i_4; if (n == 0 || n == 1 || n == 2) return 1; else if (n == 3) return 2; // base cases dp_i_4 = dp_i_3 = dp_i_2 = 1; dp_i_1 = 2; // iterate for all values from 4 to n for (int i = 4; i <= n; i++) { dp_i = dp_i_1 + dp_i_3 + dp_i_4; // Updating Variable value so in next Iteration they become relevant dp_i_4 = dp_i_3; dp_i_3 = dp_i_2; dp_i_2 = dp_i_1; dp_i_1 = dp_i; } return dp_i;}// driver codeint main() { int n = 10; cout << countWays(n); return 0;} |
Java
import java.util.*;public class Main { // function to count the number of ways to represent n as sum of 1, 3 and 4 public static int countWays(int n) { int dp_i = 0, dp_i_1, dp_i_2, dp_i_3, dp_i_4; if (n == 0 || n == 1 || n == 2) return 1; else if (n == 3) return 2; // base cases dp_i_4 = dp_i_3 = dp_i_2 = 1; dp_i_1 = 2; // iterate for all values from 4 to n for (int i = 4; i <= n; i++) { dp_i = dp_i_1 + dp_i_3 + dp_i_4; // Updating Variable value so in next Iteration they become relevant dp_i_4 = dp_i_3; dp_i_3 = dp_i_2; dp_i_2 = dp_i_1; dp_i_1 = dp_i; } return dp_i; } // driver code public static void main(String[] args) { int n = 10; System.out.println(countWays(n)); }} |
Python3
# Python program to illustrate the number of ways to represent N as sum of 1, 3 and 4.# function to count the number of ways to represent n as sum of 1, 3 and 4def countWays(n): if n == 0 or n == 1 or n == 2: return 1 elif n == 3: return 2 # base cases dp_i_4 = dp_i_3 = dp_i_2 = 1 dp_i_1 = 2 # iterate for all values from 4 to n for i in range(4, n+1): dp_i = dp_i_1 + dp_i_3 + dp_i_4 # Updating Variable value so in next Iteration they become relevant dp_i_4, dp_i_3, dp_i_2, dp_i_1 = dp_i_3, dp_i_2, dp_i_1, dp_i return dp_i# driver coden = 10print(countWays(n)) |
C#
using System;public class GFG{ // function to count the number of ways to represent n as sum of 1, 3 and 4 public static int CountWays(int n) { int dp_i = 0, dp_i_1, dp_i_2, dp_i_3, dp_i_4; if (n == 0 || n == 1 || n == 2) return 1; else if (n == 3) return 2; // base cases dp_i_4 = dp_i_3 = dp_i_2 = 1; dp_i_1 = 2; // iterate for all values from 4 to n for (int i = 4; i <= n; i++) { dp_i = dp_i_1 + dp_i_3 + dp_i_4; // Updating Variable value so in next Iteration they become relevant dp_i_4 = dp_i_3; dp_i_3 = dp_i_2; dp_i_2 = dp_i_1; dp_i_1 = dp_i; } return dp_i; } // driver code public static void Main(string[] args) { int n = 10; Console.WriteLine(CountWays(n)); }} |
Javascript
function countWays(n) { let dp_i, dp_i_1, dp_i_2, dp_i_3, dp_i_4; if (n == 0 || n == 1 || n == 2) return 1; else if (n == 3) return 2; // base cases dp_i_4 = dp_i_3 = dp_i_2 = 1; dp_i_1 = 2; // iterate for all values from 4 to n for (let i = 4; i <= n; i++) { dp_i = dp_i_1 + dp_i_3 + dp_i_4; // Updating Variable value so in next Iteration they become relevant dp_i_4 = dp_i_3; dp_i_3 = dp_i_2; dp_i_2 = dp_i_1; dp_i_1 = dp_i; } return dp_i;}// driver codelet n = 10;console.log(countWays(n)); |
Output
64
Time Complexity : O(n)
Auxiliary Space : O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
