Count of N-digit numbers with absolute difference of adjacent digits not exceeding K

Namachila November 19, 2025

0 0 10 minutes read

Given two integers N and K, the task is to find the count of N-digit numbers such that the absolute difference of adjacent digits in the number is not greater than K.

Examples:

Input: N = 2, K = 1
Output: 26
Explanation: The numbers are 10, 11, 12, 21, 22, 23, 32, 33, 34, 43, 44, 45, 54, 55, 56, 65, 66, 67, 76, 77, 78, 87, 88, 89, 98, 99

Input: N = 3, K = 2
Output: 188

Naive Approach
The simplest approach is to iterate over all N digit numbers and check for every number if the adjacent digits have an absolute difference less than or equal to K.
Time Complexity: O(10^N * N)

Efficient Approach:
To optimize the above approach, we need to use a Dynamic Programming approach along with Range Update

Initialize a DP[][] array where dp[i][j] stores the count of numbers having i digits and ending with j.
Iterate the array from 2 to N and check if the last digit was j, then the allowed digits for this place are in the range (max(0, j-k), min(9, j+k)). Perform a range update on this range.
Now use Prefix Sum to get the actual answer.

Below is the implementation of the above approach:

C++

// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return count
// of N-digit numbers with
// absolute difference of
// adjacent digits not
// exceeding K
long long getCount(int n, int k)
{
    // For 1-digit numbers,
    // the count is 10
    if (n == 1)
        return 10;
 
    long long dp[n + 1][11];
 
    // dp[i][j] stores the number
    // of such i-digit numbers
    // ending in j
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < 11; j++)
            dp[i][j] = 0;
    }
    // Initialize count for
    // 1-digit numbers
    for (int i = 1; i <= 9; i++)
        dp[1][i] = 1;
 
    // Compute values for count of
    // digits greater than 1
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= 9; j++) {
 
            // Find the range of allowed
            // numbers if last digit is j
            int l = max(0, j - k);
            int r = min(9, j + k);
 
            // Perform Range update
            dp[i][l] += dp[i - 1][j];
            dp[i][r + 1] -= dp[i - 1][j];
        }
 
        // Prefix sum to find actual
        // values of i-digit numbers
        // ending in j
        for (int j = 1; j <= 9; j++)
            dp[i][j] += dp[i][j - 1];
    }
 
    // Stores the final answer
    long long count = 0;
    for (int i = 0; i <= 9; i++)
        count += dp[n][i];
 
    return count;
}
 
// Driver Code
int main()
{
    int N = 2, K = 1;
    cout << getCount(N, K);
}

Java

// Java Program to implement
// the above approach
import java.util.*;
class GFG {
 
    // Function to return count of such numbers
    public static long getCount(int n, int k)
    {
        // For 1-digit numbers, the count
        // is 10 irrespective of K
        if (n == 1)
            return 10;
 
        // dp[i][j] stores the number
        // of such i-digit numbers
        // ending in j
        long dp[][]
            = new long[n + 1][11];
 
        // Initialize count for
        // 1-digit numbers
        for (int i = 1; i <= 9; i++)
            dp[1][i] = 1;
 
        // Compute values for count of
        // digits greater than 1
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= 9; j++) {
 
                // Find the range of allowed
                // numbers if last digit is j
                int l = Math.max(0, j - k);
                int r = Math.min(9, j + k);
 
                // Perform Range update
                dp[i][l] += dp[i - 1][j];
                dp[i][r + 1] -= dp[i - 1][j];
            }
 
            // Prefix sum to find actual values
            // of i-digit numbers ending in j
            for (int j = 1; j <= 9; j++)
                dp[i][j] += dp[i][j - 1];
        }
 
        // Stores the final answer
        long count = 0;
        for (int i = 0; i <= 9; i++)
            count += dp[n][i];
        return count;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 2, k = 1;
        System.out.println(getCount(n, k));
    }
}

Python3

# Python 3 Program to implement
# the above approach
 
# Function to return count
# of N-digit numbers with 
# absolute difference of 
# adjacent digits not
# exceeding K
def getCount(n, k):
 
    # For 1-digit numbers, the
    # count is 10
    if n == 1:
        return 10
     
    # dp[i][j] stores the count of 
    # i-digit numbers ending with j        
    dp = [[0 for x in range(11)] 
            for y in range(n + 1)];     
     
     
    # Initialize count for 
    # 1-digit numbers
    for i in range(1, 10):
        dp[1][i]= 1
     
    # Compute values for count 
    # of digits greater than 1
    for i in range(2, n + 1):
        for j in range(0, 10):
             
            # Find the range of allowed 
            # numbers if last digit is j 
            l = max(0, j - k)
            r = min(9, j + k)
                 
            # Perform Range update 
            dp[i][l] = dp[i][l] + dp[i-1][j]
            dp[i][r + 1] = dp[i][r + 1] - dp[i-1][j]
             
        # Prefix sum to find count of
        # of i-digit numbers ending with j
        for j in range(1, 10):
            dp[i][j] = dp[i][j] + dp[i][j-1]
     
    # Stores the final answer
    count = 0
     
    for i in range(0, 10):
        count = count + dp[n][i]
    return count
 
# Driver Code
n, k = 2, 1
print(getCount(n, k))

C#

// C# Program to implement
// the above approach
using System;
class GFG {
 
    // Function to return the
    // count of N-digit numbers
    // with absolute difference of
    // adjacent digits not exceeding K
    static long getCount(int n, int k)
    {
        // For 1-digit numbers, the
        // count is 10
        if (n == 1)
            return 10;
 
        // dp[i][j] stores the count of
        // i-digit numbers ending with j
        long[, ] dp = new long[n + 1, 11];
 
        // Initialize count for
        // 1-digit numbers
        for (int i = 1; i <= 9; i++)
            dp[1, i] = 1;
 
        // Compute values for count of
        // digits greater than 1
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= 9; j++) {
 
                // Find the range of allowed
                // numbers with last digit j
                int l = Math.Max(0, j - k);
                int r = Math.Min(9, j + k);
 
                // Perform Range update
                dp[i, l] += dp[i - 1, j];
                dp[i, r + 1] -= dp[i - 1, j];
            }
 
            // Prefix sum to count i-digit
            // numbers ending in j
            for (int j = 1; j <= 9; j++)
                dp[i, j] += dp[i, j - 1];
        }
 
        // Stores the final answer
        long count = 0;
        for (int i = 0; i <= 9; i++)
            count += dp[n, i];
        return count;
    }
 
    // Driver Code
    public static void Main()
    {
        int n = 2, k = 1;
        Console.WriteLine(getCount(n, k));
    }
}

Javascript

<script>
 
// Javascript implementation of 
// the above approach 
 
// Function to return count 
// of N-digit numbers with 
// absolute difference of 
// adjacent digits not 
// exceeding K 
function getCount(n, k)
{
     
    // For 1-digit numbers, the count
    // is 10 irrespective of K
    if (n == 1)
        return 10;
 
    // dp[i][j] stores the number
    // of such i-digit numbers
    // ending in j
    var dp = new Array(n + 1);
    for(var i = 0; i < dp.length; i++)
        dp[i] = Array(11).fill(0);
 
    // Initialize count for
    // 1-digit numbers
    for(i = 1; i <= 9; i++)
        dp[1][i] = 1;
 
    // Compute values for count of
    // digits greater than 1
    for(i = 2; i <= n; i++) 
    {
        for(j = 0; j <= 9; j++) 
        {
             
            // Find the range of allowed
            // numbers if last digit is j
            var l = Math.max(0, j - k);
            var r = Math.min(9, j + k);
 
            // Perform Range update
            dp[i][l] += dp[i - 1][j];
            dp[i][r + 1] -= dp[i - 1][j];
        }
 
        // Prefix sum to find actual values
        // of i-digit numbers ending in j
        for(j = 1; j <= 9; j++)
            dp[i][j] += dp[i][j - 1];
    }
 
    // Stores the final answer
    var count = 0;
    for(i = 0; i <= 9; i++)
        count += dp[n][i];
         
    return count;
}
 
// Driver Code
var n = 2, k = 1;
 
document.write(getCount(n, k));
 
// This code is contributed by umadevi9616
 
</script>

Output:

Time Complexity: O(N)
Auxiliary Space: O(N)

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 array DP of size 11 and initialize it with 0.
Set a base case and initialize initialize count for 1 digit number dp[] = 1 .
Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
Now Create a 1D array DP2 of size 11 and initialize it with 0 to store the current computation.
Create a variable count and initialize it with 0 and get the value of count by iterate through Dp.
At last return and print the count .

Implementation:

C++

// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to return count
// of N-digit numbers with
// absolute difference of
// adjacent digits not
// exceeding K
long long getCount(int n, int k)
{   
    // For 1-digit numbers,
    // the count is 10
    if (n == 1)
        return 10;
     
    // create DP and initialize it with 0
    long long dp1[11] = {0};
     
    // Initialize count for
    // 1-digit numbers
    for (int i = 1; i <= 9; i++)
        dp1[i] = 1;
  
    // iterate over subproblems ans get the current solutions
    for (int i = 2; i <= n; i++) {
        // create new DP to store current value
        long long dp2[11] = {0};
        for (int j = 0; j <= 9; j++) {
            int l = max(0, j - k);
            int r = min(9, j + k);
            for (int d = l; d <= r; d++) {
                 
                // update DP
                dp2[d] += dp1[j];
            }
        }
         
        // assigning values to iterate further
        memcpy(dp1, dp2, sizeof(dp1));
    }
     
    // create variable count 
    long long count = 0;
    for (int i = 0; i <= 9; i++)
        // update count
        count += dp1[i];
     
    // return final answer
    return count;
}
     
// Driver code
int main()
{
    int N = 2, K = 1;
     
    // function call
    cout << getCount(N, K);
}
 
// this code is contributed by bhardwajji

Java

// Java implementation of
// the above approach
import java.util.Arrays;
 
class Main 
{
   
// Function to return count
// of N-digit numbers with
// absolute difference of
// adjacent digits not
// exceeding K
static long getCount(int n, int k)
{
   
  // For 1-digit numbers,
  // the count is 10
  if (n == 1)
      return 10;
   
      // create DP and initialize it with 0
    long[] dp1 = new long[11];
    Arrays.fill(dp1, 0);
 
    // Initialize count for
    // 1-digit numbers
    for (int i = 1; i <= 9; i++)
        dp1[i] = 1;
 
    // iterate over subproblems ans get the current solutions
    for (int i = 2; i <= n; i++) {
        // create new DP to store current value
        long[] dp2 = new long[11];
        Arrays.fill(dp2, 0);
        for (int j = 0; j <= 9; j++) {
            int l = Math.max(0, j - k);
            int r = Math.min(9, j + k);
            for (int d = l; d <= r; d++) {
 
                // update DP
                dp2[d] += dp1[j];
            }
        }
 
        // assigning values to iterate further
        System.arraycopy(dp2, 0, dp1, 0, dp1.length);
    }
 
    // create variable count
    long count = 0;
    for (int i = 0; i <= 9; i++)
        // update count
        count += dp1[i];
 
    // return final answer
    return count;
}
 
// Driver code
public static void main(String[] args) {
    int N = 2, K = 1;
 
    // function call
    System.out.println(getCount(N, K));
}
}

Python3

# Function to return count
# of N-digit numbers with
# absolute difference of
# adjacent digits not
# exceeding K
def getCount(n, k):
 
    # For 1-digit numbers,
    # the count is 10
    if n == 1:
        return 10
 
    # create DP and initialize it with 0
    dp1 = [0] * 11
 
    # Initialize count for
    # 1-digit numbers
    for i in range(1, 10):
        dp1[i] = 1
 
    # iterate over subproblems and get the current solutions
    for i in range(2, n+1):
        # create new DP to store current value
        dp2 = [0] * 11
        for j in range(10):
            l = max(0, j - k)
            r = min(9, j + k)
            for d in range(l, r+1):
 
                # update DP
                dp2[d] += dp1[j]
 
        # assigning values to iterate further
        dp1 = dp2[:]
 
    # create variable count
    count = 0
    for i in range(10):
        # update count
        count += dp1[i]
 
    # return final answer
    return count
 
# Driver code
if __name__ == '__main__':
    N, K = 2, 1
 
    # function call
    print(getCount(N, K))

Javascript

// Function to return count
// of N-digit numbers with
// absolute difference of
// adjacent digits not
// exceeding K
function getCount(n, k) {
 
  // For 1-digit numbers,
  // the count is 10
  if (n == 1) {
    return 10;
  }
 
  // create DP and initialize it with 0
  let dp1 = new Array(11).fill(0);
 
  // Initialize count for
  // 1-digit numbers
  for (let i = 1; i < 10; i++) {
    dp1[i] = 1;
  }
 
  // iterate over subproblems and get the current solutions
  for (let i = 2; i <= n; i++) {
    // create new DP to store current value
    let dp2 = new Array(11).fill(0);
    for (let j = 0; j < 10; j++) {
      let l = Math.max(0, j - k);
      let r = Math.min(9, j + k);
      for (let d = l; d <= r; d++) {
 
        // update DP
        dp2[d] += dp1[j];
      }
    }
 
    // assigning values to iterate further
    dp1 = dp2.slice();
  }
 
  // create variable count
  let count = 0;
  for (let i = 0; i < 10; i++) {
    // update count
    count += dp1[i];
  }
 
  // return final answer
  return count;
}
 
// Driver code
let N = 2, K = 1;
 
// function call
console.log(getCount(N, K));

Output

Time Complexity: O(N)
Auxiliary Space: O(1) <= O(11)

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!