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.

advertisement
advertisement

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:

Note: Join free Sanfoundry classes at Telegram or Youtube
 
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.

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

advertisement

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.