Counting numbers of n digits that are monotone

0 0 7 minutes read

Call decimal number a monotone if: $D[\, i]\, \leqslant D[\, i+1]\, 0 \leqslant i \leqslant |D|$ . 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: $\{111\}, \{123\}, \{12223333444\}$ All those numbers are monotone as each digit on higher place is $\geq$ 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: $\{1\}, \{2\}$ That was easy, now lets expand the question to digits 1, 2 and 3: $\{1\}, \{2\}, \{3\}$ Now different question, what are the different monotone numbers consisting of only 1 and length 3 are there? $\{111\}$ 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: $\begin{array}{c c c c c c c c c c} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &\\ 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &\\ 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &\\ 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &\\ \end{array}$ 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: $\{11\}, \{12\}, \{22\}$ If we will look closer we already have subsets of this set i.e: $\{11\}, \{12\}$ – Monotone numbers that has length 2 and consist of 1 or 2 $\{22\}$ – 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: $\begin{array}{c c c c c c c c c c} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &\\ 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &\\ 2 & 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 47 &\\ 3 & 1 & 4 & 10 & 20 & 35 & 56 & 84 & 120 & 167 &\\ \end{array}$

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 = 9
 
def 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 code
print(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 code
echo 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 = 9
 
function 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 code
document.write(getNumMonotone(10),"</br>")
 
 
// This code is contributed by shinjanpatra
 
</script>

Output

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 code
int 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 code
static void Main()
{
    // function call
    Console.WriteLine(GetNumMonotone(10));
}
}

Output

Time complexity: O(n*DP_s)
Auxiliary space: O(DP_s)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!