Total number of non-decreasing numbers with n digits

December 7, 2021

Total number of non-decreasing numbers with n digits

In the total number of non-decreasing numbers problem, we have to find all numbers of length 1 to n such that the digits in numbers are in increasing order. The problem can be solved using dynamic programming. In the article, we will provide a C++ solution with an explanation.

Total number of non-decreasing numbers with n digits

Total number of non-decreasing numbers Problem Description

Given an integer n. Return the count of all numbers of length 1 to n such that the digits in each number are in non – decreasing order from left to right.
Eg – 33221 is a valid number but 123 is not a valid number.

Input:

  • First-line contains integer n.

Output:

  • Single Integer, the required count.

Total number of non-decreasing numbers Problem Solution

Steps required are –

Function Definition –Let F(id,prev) = no. of numbers such that digit prev is placed at position id-1.

Recursive Calls  – We know digit prev was filled at position id – 1. So for current position we will iterate for all digits from prev to 9. This will ensure that we are generating numbers such that their digits are in increasing order from left to right.

Memorization – It is easy to observe that we have overlapping sub-problems and optimal substructure. Now we can create a dp table and memoize our solution.

Time Complexity – O(10*n)

Space Complexity – O(10*n)

Code

#include <bits/stdc++.h>
using namespace std;
int n;
int dp[15][15];
/*
    idx = current position
    prev = prev digit used
*/
int numbers(int idx, int prev)
{
    // Base case
    if (idx == n)
        return 1;

    if (dp[idx][prev] != –1)
        return dp[idx][prev];

    int count = 0;
    // since we want increasing numbers using all digits from prev to 9 for current position
    for (int i = prev; i <= 9; i++)
    {
        count += numbers(idx + 1, i);
    }
    return dp[idx][prev] = count;
}
int main()
{
    cin >> n;
    memset(dp, –1, sizeof dp);

    cout << numbers(0, 0) << endl;
}

Output

2
55