Count of different ways to express N as the sum of 1, 3 and 4

19 June 2025

0

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:

DP_{n = 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 4
int 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 code
int 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 4
def 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 = 10
print (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 4
function 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 4
function 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 code
var n = 10;
 
document.write(countWays(n));
 
// This code is contributed by bunnyram19   
 
</script>

Output

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 4
int 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 code
int 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 4
def 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 code
n = 10
print(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 code
let n = 10;
console.log(countWays(n));

Output

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!

Count of different ways to express N as the sum of 1, 3 and 4

C++

Java

Python3

C#

PHP

Javascript

C++

Java

Python3

C#

Javascript

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US