Call decimal number a monotone if: ![D[\, i]\, \leqslant D[\, i+1]\, 0 \leqslant i \leqslant |D|](https://geeksforgeeks.org/wp-content/uploads/2023/10/dominic_rubhabha_quicklatex.com-e25fb616bc3bcef052b390f069c926f3_l3.png "Rendered by QuickLaTeX.com")
. Write a program that takes the positive number n on input and returns a number of decimal numbers of length n that are monotone. Numbers can’t start with 0.
Examples :
Input : 1 Output : 9 Numbers are 1, 2, 3, ... 9 Input : 2 Output : 45 Numbers are 11, 12, 13, .... 22, 23 ...29, 33, 34, ... 39. Count is 9 + 8 + 7 ... + 1 = 45
Explanation: Let’s start by example of monotone numbers:
All those numbers are monotone as each digit on higher place is 
than the one before it. What are the monotone numbers are of length 1 and digits 1 or 2? It is question to ask yourself at the very beginning. We can see that possible numbers are: 
That was easy, now lets expand the question to digits 1, 2 and 3: 
Now different question, what are the different monotone numbers consisting of only 1 and length 3 are there? 
Lets try now draw this very simple observation in 2 dimensional array for number of length 3, where first column is the length of string and first row is possible digits: 
Let’s try to fill 3rd row 3rd column(number of monotone numbers consisting from numbers 1 or 2 with length 2). This should be: 
If we will look closer we already have subsets of this set i.e: 
– Monotone numbers that has length 2 and consist of 1 or 2 
– Monotone numbers of length 2 and consisting of number 2 We just need to add previous values to get the longer one. Final matrix should look like this: 
C++
// CPP program to count numbers of n digits// that are monotone.#include <cstring>#include <iostream>// Considering all possible digits as {1, 2, 3, ..9}int static const DP_s = 9;int getNumMonotone(int len){ // DP[i][j] is going to store monotone numbers of length // i+1 considering j+1 digits. int DP[len][DP_s]; memset(DP, 0, sizeof(DP)); // Unit length numbers for (int i = 0; i < DP_s; ++i) DP[0][i] = i + 1; // Single digit numbers for (int i = 0; i < len; ++i) DP[i][0] = 1; // Filling rest of the entries in bottom // up manner. for (int i = 1; i < len; ++i) for (int j = 1; j < DP_s; ++j) DP[i][j] = DP[i - 1][j] + DP[i][j - 1]; return DP[len - 1][DP_s - 1];}// Driver code.int main(){ std::cout << getNumMonotone(10); return 0;}// This code is contributed by Sania Kumari Gupta |
C
// C program to count numbers of n digits// that are monotone.#include <stdio.h>#include <string.h>// Considering all possible digits as// {1, 2, 3, ..9}int static const DP_s = 9;int getNumMonotone(int len){ // DP[i][j] is going to store monotone numbers of length // i+1 considering j+1 digits. int DP[len][DP_s]; memset(DP, 0, sizeof(DP)); // Unit length numbers for (int i = 0; i < DP_s; ++i) DP[0][i] = i + 1; // Single digit numbers for (int i = 0; i < len; ++i) DP[i][0] = 1; // Filling rest of the entries in bottom up manner. for (int i = 1; i < len; ++i) for (int j = 1; j < DP_s; ++j) DP[i][j] = DP[i - 1][j] + DP[i][j - 1]; return DP[len - 1][DP_s - 1];}// Driver code.int main(){ printf("%d", getNumMonotone(10)); return 0;}// This code is contributed by Sania Kumari Gupta |
Java
// Java program to count numbers // of n digits that are monotone.class GFG { // Considering all possible // digits as {1, 2, 3, ..9} static final int DP_s = 9; static int getNumMonotone(int len) { // DP[i][j] is going to store // monotone numbers of length // i+1 considering j+1 digits. int[][] DP = new int[len][DP_s]; // Unit length numbers for (int i = 0; i < DP_s; ++i) DP[0][i] = i + 1; // Single digit numbers for (int i = 0; i < len; ++i) DP[i][0] = 1; // Filling rest of the entries // in bottom up manner. for (int i = 1; i < len; ++i) for (int j = 1; j < DP_s; ++j) DP[i][j] = DP[i - 1][j] + DP[i][j - 1]; return DP[len - 1][DP_s - 1]; } // Driver code. public static void main (String[] args) { System.out.println(getNumMonotone(10)); }}// This code is contributed by Ansu Kumari. |
Python3
# Python3 program to count numbers of n # digits that are monotone.# Considering all possible digits as# {1, 2, 3, ..9}DP_s = 9def getNumMonotone(ln): # DP[i][j] is going to store monotone # numbers of length i+1 considering # j+1 digits. DP = [[0]*DP_s for i in range(ln)] # Unit length numbers for i in range(DP_s): DP[0][i] = i + 1 # Single digit numbers for i in range(ln): DP[i][0] = 1 # Filling rest of the entries # in bottom up manner. for i in range(1, ln): for j in range(1, DP_s): DP[i][j] = DP[i - 1][j] + DP[i][j - 1] return DP[ln - 1][DP_s - 1]# Driver codeprint(getNumMonotone(10))# This code is contributed by Ansu Kumari |
C#
// C# program to count numbers // of n digits that are monotone.using System;class GFG { // Considering all possible // digits as {1, 2, 3, ..9} static int DP_s = 9; static int getNumMonotone(int len) { // DP[i][j] is going to store // monotone numbers of length // i+1 considering j+1 digits. int[,] DP = new int[len,DP_s]; // Unit length numbers for (int i = 0; i < DP_s; ++i) DP[0,i] = i + 1; // Single digit numbers for (int i = 0; i < len; ++i) DP[i,0] = 1; // Filling rest of the entries // in bottom up manner. for (int i = 1; i < len; ++i) for (int j = 1; j < DP_s; ++j) DP[i,j] = DP[i - 1,j] + DP[i,j - 1]; return DP[len - 1,DP_s - 1]; } // Driver code. public static void Main () { Console.WriteLine(getNumMonotone(10)); }}// This code is contributed by vt_m. |
PHP
<?php// PHP program to count numbers // of n digits that are monotone.function getNumMonotone($len){ // Considering all possible // digits as {1, 2, 3, ..9} $DP_s = 9; // DP[i][j] is going to store // monotone numbers of length // i+1 considering j+1 digits. $DP = array(array_fill(0, $len, 0), array_fill(0, $len, 0)); // Unit length numbers for ($i = 0; $i < $DP_s; ++$i) $DP[0][$i] = $i + 1; // Single digit numbers for ($i = 0; $i < $len; ++$i) $DP[$i][0] = 1; // Filling rest of the entries // in bottom up manner. for ($i = 1; $i < $len; ++$i) for ($j = 1; $j < $DP_s; ++$j) $DP[$i][$j] = $DP[$i - 1][$j] + $DP[$i][$j - 1]; return $DP[$len - 1][$DP_s - 1];}// Driver codeecho getNumMonotone(10);// This code is contributed by mits?> |
Javascript
<script>// JavaScript program to count numbers of n// digits that are monotone.// Considering all possible digits as// {1, 2, 3, ..9}let DP_s = 9function getNumMonotone(ln){ // DP[i][j] is going to store monotone // numbers of length i+1 considering // j+1 digits. let DP = new Array(ln).fill(0).map(()=>new Array(DP_s).fill(0)) // Unit length numbers for(let i=0;i<DP_s;i++){ DP[0][i] = i + 1 } // Single digit numbers for(let i=0;i<ln;i++) DP[i][0] = 1 // Filling rest of the entries // in bottom up manner. for(let i=1;i<ln;i++){ for(let j=1;j<DP_s;j++){ DP[i][j] = DP[i - 1][j] + DP[i][j - 1] } } return DP[ln - 1][DP_s - 1]}// Driver codedocument.write(getNumMonotone(10),"</br>")// This code is contributed by shinjanpatra</script> |
Output
43758
Time complexity: O(n*DP_s)
Auxiliary space: O(n*DP_s)
Efficient approach : Space optimization
In previous approach the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation steps:
- Create a 1D vector dp of size DP_s.
- Set a base case by initializing the values of DP .
- Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
- At last return and print the final answer stored dp[Dp_s-1] .
Implementation:
C++
// CPP program to count numbers of n digits// that are monotone.#include <cstring>#include <iostream>// Considering all possible digits as {1, 2, 3, ..9}int static const DP_s = 9;// funtion to count numbers of n digits// that are monotone.int getNumMonotone(int len){ int DP[DP_s]; memset(DP, 0, sizeof(DP)); for (int i = 0; i < DP_s; ++i) DP[i] = i + 1; // iterate over subprobelms for (int i = 1; i < len; ++i) for (int j = 1; j < DP_s; ++j) DP[j] += DP[j - 1]; // return answer return DP[DP_s - 1];}// Driver codeint main(){ // function call std::cout << getNumMonotone(10); return 0;} |
C#
// C# program to count numbers of n digits// that are monotone.using System;class GFG{ // Considering all possible digits as {1, 2, 3, ..9}const int DP_s = 9; // function to count numbers of n digits// that are monotone.static int GetNumMonotone(int len){ int[] DP = new int[DP_s]; for (int i = 0; i < DP_s; ++i) DP[i] = i + 1; // iterate over subproblems for (int i = 1; i < len; ++i) for (int j = 1; j < DP_s; ++j) DP[j] += DP[j - 1]; // return answer return DP[DP_s - 1];}// Driver codestatic void Main(){ // function call Console.WriteLine(GetNumMonotone(10));}} |
Output
43758
Time complexity: O(n*DP_s)
Auxiliary space: O(DP_s)
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
