This is a C++ Program that Solves Non Decreasing Digits Problem using Dynamic Programming technique.
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.
Constraints
A decimal integer giving the number of digits N, (1 <= N <= 64)
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.
Case-1:
number of digits=2 Expected result=55
Case-2:
number of digits=3 Expected result=220
Case-3:
number of digits=4 Expected result=715
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.
//non decreasing digits
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i,j;
int n;
//number of digits
cout<<"Enter the number of digits "<<endl;
cin>>n;
//matrix to memoize values
vector<vector<long long int> > a(10,vector<long long int>(n+1,0));
//a[j][i]=count of all possible number with i digits having leading digit j
//initialization
for(i=0;i<=9;i++)
a[i][0]=1;
for(i=1;i<=n;i++)
a[9][i]=1;
//for all digits
for(i=1;i<=n;i++)
{
for(j=8;j>=0;j--)
{
a[j][i]=a[j][i-1]+a[j+1][i];
}
}
//result
cout<<"Count of all valid "<<n<<" digit number with non-decreasing digits are "<<endl;
cout<<a[0][n]<<endl;
return 0;
}
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.
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.
- Check Data Structure Books
- Check Computer Science Books
- Apply for Computer Science Internship
- Practice Programming MCQs
- Practice Computer Science MCQs