# Non Decreasing Digits Problem – Dynamic Programming Solutions

«
»

This is a C++ Program that Solves Non Decreasing Digits Problem using Dynamic Programming technique.

Problem Description

A number is said to be made up of non-decreasing digits if all the digits to the left of any digit is less than or equal to that digit.

For example, the four-digit number 1234 is composed of digits that are non-decreasing.

Some other four-digit numbers that are composed of non-decreasing digits are 0011, 1111, 1112, 1122, 2223. As it turns out, there are exactly 715 four-digit numbers composed of non-decreasing digits.

Notice that leading zeroes are required: 0000, 0001, 0002 are all valid four-digit numbers with non-decreasing digits.

For this problem, you will write a program that determines how many such numbers there are with a specified number of digits.

Note: Join free Sanfoundry classes at Telegram or Youtube

Constraints
A decimal integer giving the number of digits N, (1 <= N <= 64)

Problem Solution

In this problem, we create a matrix a[][] where a[i][j]=count of all valid j digit numbers with i as the leading digit. We will fill this matrix row wise, first calculating a[9][1] then using this value to compute a[8][2] and so on.

Expected Input and Output

Case-1:

number of digits=2
Expected result=55

Case-2:

Take Data Structure I Mock Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

number of digits=3
Expected result=220

Case-3:

number of digits=4
Expected result=715
Program/Source Code

Here is source code of the C++ Program to Solve Non Decreasing digits problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1.
2. //non decreasing digits
3. #include<bits/stdc++.h>
4. using namespace std;
5.
6. int main()
7. {
8.     int i,j;
9.     int n;
10.
11.     //number of digits
12.     cout<<"Enter the number of digits "<<endl;
13.     cin>>n;
14.
15.     //matrix to memoize values
16.     vector<vector<long long int> > a(10,vector<long long int>(n+1,0));
17.
18.     //a[j][i]=count of all possible number with i digits having leading digit j
19.
20.     //initialization
21.     for(i=0;i<=9;i++)
22.         a[i][0]=1;
23.
24.     for(i=1;i<=n;i++)
25.         a[9][i]=1;
26.
27.     //for all digits
28.     for(i=1;i<=n;i++)
29.     {
30.         for(j=8;j>=0;j--)
31.         {
32.             a[j][i]=a[j][i-1]+a[j+1][i];
33.         }
34.     }
35.
36.     //result
37.     cout<<"Count of all valid "<<n<<" digit number with non-decreasing digits are "<<endl;
38.     cout<<a[0][n]<<endl;
39.
40.     return 0;
41. }
Program Explanation

In the main function, we take the number of digits, n as the input. A matrix is created to store the result of overlapping subproblems. After filling the matrix in a bottom up manner, the result is displayed.

Runtime Test Cases

Case-1:
\$ g++ non_decreasing_digits.cpp
\$ ./a.out
Enter the number of digits
2
Count of all valid 2 digit number with non-decreasing digits are
55

Case-2:
\$ ./a.out
Enter the number of digits
3
Count of all valid 3 digit number with non-decreasing digits are
220

Case-3:
\$ ./a.out
Enter the number of digits
4
Count of all valid 4 digit number with non-decreasing digits are
715

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.