Count N-digit numbers whose digits does not exceed absolute difference of the two previous digits

0 0 7 minutes read

Given an integer N, the task is to count the number of N-digit numbers such that each digit, except the first and second digits, is less than or equal to the absolute difference of the previous two digits.

Examples:

Input: N = 1
Output: 10
Explanation: All the numbers from [0 – 9] are valid because the number of digits is 1.

Input : N = 3
Output : 375

Naive Approach: The simplest approach is to iterate over all possible N-digit numbers and for each such numbers, check if all its digits satisfy the above condition or not.

Time Complexity: O(10^N*N)
Auxiliary Space: O(1)

Efficient Approach: In the efficient approach, all possible numbers are constructed instead of verifying the conditions on a range of numbers. This can be achieved with the help of Dynamic Programming because it has overlapping subproblems and optimal substructure. The subproblems can be stored in dp[][][] table using memoization where dp[digit][prev1][prev2] stores the answer from the digit-th position till the end, when the previous digit selected, is prev1 and the second most previous digit selected is prev2.

Follow the below steps to solve the problem:

Define a recursive function countOfNumbers(digit, prev1, prev2) by performing the following steps.
- Check the base cases. If the value of digit is equal to N+1 then return 1 as a valid N-digit number is formed.
- If the result of the state dp[digit][prev1][prev2] is already computed, return this state dp[digit][prev1][prev2].
- If the current digit is 1, then any digit from [1-9] can be placed. If N=1, then 0 can be placed as well.
- If the current digit is 2, then any digit from [0-9] can be placed.
- Else any number from [0-(abs(prev1-prev2))] can be placed at the current position.
- After making a valid placement, recursively call the countOfNumbers function for index digit+1.
- Return the sum of all possible valid placements of digits as the answer.

Below is the code for the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
long long dp[50][10][10];
 
// Function to count N digit numbers whose
// digits are less than or equal to the
// absolute difference of previous two digits
long long countOfNumbers(int digit, int prev1,
                         int prev2, int N)
{
    // If all digits are traversed
    if (digit == N + 1)
        return 1;
 
    // If the state has already been computed
    if (dp[digit][prev1][prev2] != -1)
        return dp[digit][prev1][prev2];
 
    dp[digit][prev1][prev2] = 0;
 
    // If the current digit is 1,
    // any digit from [1-9] can be placed.
    // If N==1, 0 can also be placed.
    if (digit == 1) {
        for (int j = (N == 1 ? 0 : 1);
             j <= 9; ++j) {
 
            dp[digit][prev1][prev2]
                += countOfNumbers(digit + 1,
                                  j, prev1, N);
        }
    }
 
    // If the current digit is 2, any
    // digit from [0-9] can be placed
    else if (digit == 2) {
        for (int j = 0; j <= 9; ++j) {
 
            dp[digit][prev1][prev2]
                += countOfNumbers(
                    digit + 1, j, prev1, N);
        }
    }
 
    // For other digits, any digit
    // from 0 to abs(prev1 - prev2) can be placed
    else {
        for (int j = 0; j <= abs(prev1 - prev2); ++j) {
 
            dp[digit][prev1][prev2]
                += countOfNumbers(digit + 1, j, prev1, N);
        }
    }
 
    // Return the answer
    return dp[digit][prev1][prev2];
}
 
// Driver code
int main()
{
    // Initializing dp array with -1.
    memset(dp, -1, sizeof dp);
 
    // Input
    int N = 3;
 
    // Function call
    cout << countOfNumbers(1, 0, 0, N) << endl;
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
static int dp[][][] = new int[50][10][10];
 
static void initialize()
{
    for(int i = 0; i < 50; i++)
    {
        for(int j = 0; j < 10; j++)
        {
            for(int k = 0; k < 10; k++)
            {
                dp[i][j][k] = -1;
            }
        }
    }
}
  
// Function to count N digit numbers whose
// digits are less than or equal to the
// absolute difference of previous two digits
static int countOfNumbers(int digit, int prev1,
                          int prev2, int N)
{
     
    // If all digits are traversed
    if (digit == N + 1)
        return 1;
  
    // If the state has already been computed
    if (dp[digit][prev1][prev2] != -1)
        return dp[digit][prev1][prev2];
  
    dp[digit][prev1][prev2] = 0;
  
    // If the current digit is 1,
    // any digit from [1-9] can be placed.
    // If N==1, 0 can also be placed.
    if (digit == 1) 
    {
        for(int j = (N == 1 ? 0 : 1);
                j <= 9; ++j) 
        {
            dp[digit][prev1][prev2] += countOfNumbers(
                digit + 1, j, prev1, N);
        }
    }
  
    // If the current digit is 2, any
    // digit from [0-9] can be placed
    else if (digit == 2) 
    {
        for(int j = 0; j <= 9; ++j) 
        {
            dp[digit][prev1][prev2] += countOfNumbers(
                    digit + 1, j, prev1, N);
        }
    }
  
    // For other digits, any digit
    // from 0 to abs(prev1 - prev2) can be placed
    else
    {
        for(int j = 0; j <= Math.abs(prev1 - prev2); ++j)
        {
            dp[digit][prev1][prev2] += countOfNumbers(
                digit + 1, j, prev1, N);
        }
    }
  
    // Return the answer
    return dp[digit][prev1][prev2];
}
     
// Driver Code
public static void main(String[] args)
{
    initialize();
      
    // Input
    int N = 3;
  
    // Function call
    System.out.print(countOfNumbers(1, 0, 0, N));
}
}
 
// This code is contributed by susmitakundugoaldanga

Python3

# Python3 program for the above approach
dp = [[[-1 for i in range(10)] 
           for j in range(10)] 
           for k in range(50)]
 
# Function to count N digit numbers whose
# digits are less than or equal to the
# absolute difference of previous two digits
def countOfNumbers(digit, prev1, prev2, N):
     
    # If all digits are traversed
    if (digit == N + 1):
        return 1
 
    # If the state has already been computed
    if (dp[digit][prev1][prev2] != -1):
        return dp[digit][prev1][prev2]
 
    dp[digit][prev1][prev2] = 0
 
    # If the current digit is 1,
    # any digit from [1-9] can be placed.
    # If N==1, 0 can also be placed.
    if (digit == 1):
        term = 0 if N == 1 else 1
         
        for j in range(term, 10, 1):
            dp[digit][prev1][prev2] += countOfNumbers(
                digit + 1, j, prev1, N)
 
    # If the current digit is 2, any
    # digit from [0-9] can be placed
    elif (digit == 2):
        for j in range(10):
            dp[digit][prev1][prev2] += countOfNumbers(
                digit + 1, j, prev1, N)
 
    # For other digits, any digit
    # from 0 to abs(prev1 - prev2) can be placed
    else:
        for j in range(abs(prev1 - prev2) + 1):
            dp[digit][prev1][prev2] += countOfNumbers(
                digit + 1, j, prev1, N)
 
    # Return the answer
    return dp[digit][prev1][prev2]
 
# Driver code
if __name__ == '__main__':
     
    # Input
    N = 3
     
    # Function call
    print(countOfNumbers(1, 0, 0, N))
     
# This code is contributed by ipg2016107

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
static int [,,]dp = new int[50, 10, 10];
 
static void initialize()
{
    for(int i = 0; i < 50; i++)
    {
        for(int j = 0; j < 10; j++)
        {
            for(int k = 0; k < 10; k++)
            {
                dp[i, j, k] = -1;
            }
        }
    }
}
 
// Function to count N digit numbers whose
// digits are less than or equal to the
// absolute difference of previous two digits
static int countOfNumbers(int digit, int prev1,
                          int prev2, int N)
{
     
    // If all digits are traversed
    if (digit == N + 1)
        return 1;
 
    // If the state has already been computed
    if (dp[digit, prev1, prev2] != -1)
        return dp[digit, prev1, prev2];
 
    dp[digit, prev1, prev2] = 0;
 
    // If the current digit is 1,
    // any digit from [1-9] can be placed.
    // If N==1, 0 can also be placed.
    if (digit == 1) 
    {
        for(int j = (N == 1 ? 0 : 1);
                j <= 9; ++j)
        {
            dp[digit, prev1, prev2] += countOfNumbers(
                              digit + 1, j, prev1, N);
        }
    }
 
    // If the current digit is 2, any
    // digit from [0-9] can be placed
    else if (digit == 2)
    {
        for(int j = 0; j <= 9; ++j) 
        {
            dp[digit, prev1, prev2] += countOfNumbers(
                              digit + 1, j, prev1, N);
        }
    }
 
    // For other digits, any digit
    // from 0 to abs(prev1 - prev2)
    // can be placed
    else
    {
        for(int j = 0; j <= Math.Abs(prev1 - prev2); ++j) 
        {
            dp[digit, prev1, prev2] += countOfNumbers(
                              digit + 1, j, prev1, N);
        }
    }
 
    // Return the answer
    return dp[digit, prev1, prev2];
}
 
// Driver code
public static void Main()
{
    initialize();
     
    // Input
    int N = 3;
 
    // Function call
    Console.Write(countOfNumbers(1, 0, 0, N));
}
}
 
// This code is contributed by SURENDRA_GANGWAR

Javascript

<script>
 
// JavaScript program for the above approach
 
 
var dp = Array.from(Array(50), ()=>Array(10));
for(var i =0; i<10; i++)
        for(var j =0; j<10; j++)
            dp[i][j] = new Array(10).fill(-1); 
 
// Function to count N digit numbers whose
// digits are less than or equal to the
// absolute difference of previous two digits
function countOfNumbers(digit, prev1, prev2, N)
{
    // If all digits are traversed
    if (digit == N + 1)
        return 1;
 
    // If the state has already been computed
    if (dp[digit][prev1][prev2] != -1)
        return dp[digit][prev1][prev2];
 
    dp[digit][prev1][prev2] = 0;
 
    // If the current digit is 1,
    // any digit from [1-9] can be placed.
    // If N==1, 0 can also be placed.
    if (digit == 1) {
        for (var j = (N == 1 ? 0 : 1);
             j <= 9; ++j) {
 
            dp[digit][prev1][prev2]
                += countOfNumbers(digit + 1,
                                  j, prev1, N);
        }
    }
 
    // If the current digit is 2, any
    // digit from [0-9] can be placed
    else if (digit == 2) {
        for (var j = 0; j <= 9; ++j) {
 
            dp[digit][prev1][prev2]
                += countOfNumbers(
                    digit + 1, j, prev1, N);
        }
    }
 
    // For other digits, any digit
    // from 0 to abs(prev1 - prev2) can be placed
    else {
        for (var j = 0; j <= Math.abs(prev1 - prev2); ++j) {
 
            dp[digit][prev1][prev2]
                += countOfNumbers(digit + 1, j, prev1, N);
        }
    }
 
    // Return the answer
    return dp[digit][prev1][prev2];
}
 
// Driver code
 
// Input
var N = 3;
 
// Function call
document.write( countOfNumbers(1, 0, 0, N));
 
</script>

Output:

Time Complexity : O(N * 10³)
Auxiliary Space: O(N * 10²)

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!