Count of N digit numbers having absolute difference between adjacent digits as K

Namachila November 19, 2025

0 0 6 minutes read

Given two integers N and K. The task is to count all positive integers with length N having an absolute difference between adjacent digits equal to K.

Examples:

Input: N = 4, K = 8
Output: 3
Explanation: The absolute difference between every consecutive digit of each number is 8. Three possible numbers are 8080, 1919 and 9191.

Input: N = 2, K = 0
Output: 9
Explanation: 11, 22, 33, 44, 55, 66, 77, 88, 99. The absolute difference between every consecutive digit of each number is 0.

Approach: The approach is based on recursion. Iterate over digits [1, 9], and for each digit, count the N-digit number having a difference of absolute digit as K using recursion. Following cases arrive in the recursive function call.

Base Case: For all single-digit integers i.e. N = 1, increment answer count.
Recursive Call: If adding digit K to the one’s digit of the number formed till now (num) does not exceed 9, then recursively call by decreasing N and making num = (num*10 + num%10 + K).

if(num % 10 + K ≤ 9)
recursive_function(10 * num + (num % 10 + K), N – 1);

If the value of K is non-zero after all the recursive calls and if num % 10 ≥ K, then again recursively call by decreasing the N and update num to (10*num + num%10 – K).

if(num % 10 ≥ K)
recursive_function(10 * num + num % 10 – K, N – 1)

Below is the implementation of the above approach.

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// To store the count of numbers
int countNums = 0;
 
// Function that recursively finds the
// possible numbers and append into ans
void checkUtil(int num, int K, int N)
{
    // Base Case
    if (N == 1) {
        countNums++;
        return;
    }
 
    // Check the sum of last digit and k
    // less than or equal to 9 or not
    if ((num % 10 + K) <= 9)
        checkUtil(10 * num + 
                  (num % 10 + K), K, N - 1);
 
    // If K = 0, then subtraction and
    // addition does not make any
    // difference
    if (K) {
         
        // If unit's digit greater than K
        if ((num % 10 - K) >= 0)
            checkUtil(10 * num +
                      num % 10 - K, K, N - 1);
    }
}
 
// Function to call checkUtil function
// for every integer from 1 to 9
void check(int K, int N)
{
    // Loop to check for 
    // all digits from 1 to 9
    for (int i = 1; i <= 9; i++) {
        checkUtil(i, K, N);
    }
}
 
// Driver Code
int main()
{
    // Given N and K
    int N = 4, K = 8;
    check(K, N);
 
    // Count total possible numbers
    cout << countNums << endl;
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// To store the count of numbers
static int countNums = 0;
 
// Function that recursively finds the
// possible numbers and append into ans
static void checkUtil(int num, int K, int N)
{
   
    // Base Case
    if (N == 1) {
        countNums++;
        return;
    }
 
    // Check the sum of last digit and k
    // less than or equal to 9 or not
    if ((num % 10 + K) <= 9)
        checkUtil(10 * num + 
                  (num % 10 + K), K, N - 1);
 
    // If K = 0, then subtraction and
    // addition does not make any
    // difference
    if (K>0) {
         
        // If unit's digit greater than K
        if ((num % 10 - K) >= 0)
            checkUtil(10 * num +
                      num % 10 - K, K, N - 1);
    }
}
 
// Function to call checkUtil function
// for every integer from 1 to 9
static void check(int K, int N)
{
   
    // Loop to check for 
    // all digits from 1 to 9
    for (int i = 1; i <= 9; i++) {
        checkUtil(i, K, N);
    }
}
 
// Driver Code
public static void main(String[] args)
{
   
    // Given N and K
    int N = 4, K = 8;
    check(K, N);
 
    // Count total possible numbers
    System.out.print(countNums +"\n");
}
}
 
// This code contributed by shikhasingrajput

Python3

# Python program for the above approach
 
# To store the count of numbers
countNums = 0;
 
# Function that recursively finds the
# possible numbers and append into ans
def checkUtil(num, K, N):
    global countNums;
     
    # Base Case
    if (N == 1):
        countNums += 1;
        return;
 
    # Check the sum of last digit and k
    # less than or equal to 9 or not
    if ((num % 10 + K) <= 9):
        checkUtil(10 * num + (num % 10 + K), K, N - 1);
 
    # If K = 0, then subtraction and
    # addition does not make any
    # difference
    if (K > 0):
 
        # If unit's digit greater than K
        if ((num % 10 - K) >= 0):
            checkUtil(10 * num + num % 10 - K, K, N - 1);
 
# Function to call checkUtil function
# for every integer from 1 to 9
def check(K, N):
   
    # Loop to check for
    # all digits from 1 to 9
    for i in range(1,10):
        checkUtil(i, K, N);
 
# Driver Code
if __name__ == '__main__':
    # Given N and K
    N = 4;
    K = 8;
    check(K, N);
 
    # Count total possible numbers
    print(countNums);
 
# This code is contributed by shikhasingrajput

C#

// C# program for the above approach
using System;
 
class GFG{
 
// To store the count of numbers
static int countNums = 0;
 
// Function that recursively finds the
// possible numbers and append into ans
static void checkUtil(int num, int K, int N)
{
     
    // Base Case
    if (N == 1)
    {
        countNums++;
        return;
    }
 
    // Check the sum of last digit and k
    // less than or equal to 9 or not
    if ((num % 10 + K) <= 9)
        checkUtil(10 * num + 
                 (num % 10 + K), K, N - 1);
 
    // If K = 0, then subtraction and
    // addition does not make any
    // difference
    if (K > 0) 
    {
         
        // If unit's digit greater than K
        if ((num % 10 - K) >= 0)
            checkUtil(10 * num +
                      num % 10 - K, K, N - 1);
    }
}
 
// Function to call checkUtil function
// for every integer from 1 to 9
static void check(int K, int N)
{
     
    // Loop to check for 
    // all digits from 1 to 9
    for(int i = 1; i <= 9; i++) 
    {
        checkUtil(i, K, N);
    }
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given N and K
    int N = 4, K = 8;
    check(K, N);
 
    // Count total possible numbers
    Console.Write(countNums + "\n");
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
      // JavaScript code for the above approach
 
      // To store the count of numbers
      let countNums = 0;
 
      // Function that recursively finds the
      // possible numbers and append into ans
      function checkUtil(num, K, N) 
      {
       
          // Base Case
          if (N == 1) {
              countNums++;
              return;
          }
 
          // Check the sum of last digit and k
          // less than or equal to 9 or not
          if ((num % 10 + K) <= 9)
              checkUtil(10 * num +
                  (num % 10 + K), K, N - 1);
 
          // If K = 0, then subtraction and
          // addition does not make any
          // difference
          if (K) {
 
              // If unit's digit greater than K
              if ((num % 10 - K) >= 0)
                  checkUtil(10 * num +
                      num % 10 - K, K, N - 1);
          }
      }
 
      // Function to call checkUtil function
      // for every integer from 1 to 9
      function check(K, N) 
      {
       
          // Loop to check for 
          // all digits from 1 to 9
          for (let i = 1; i <= 9; i++) {
              checkUtil(i, K, N);
          }
      }
 
      // Driver Code
 
      // Given N and K
      let N = 4, K = 8;
      check(K, N);
 
      // Count total possible numbers
      document.write(countNums + '<br>');
 
// This code is contributed by Potta Lokesh
  </script>

Output

Time Complexity: O(2^N)
Auxiliary Space: O(1)

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!