Data Modelling & AI Data Structure & Algorithm

Generate all N digit numbers having absolute difference as K between adjacent digits

23 June 2025

0

Given two integers N and K, the task is to generate all positive integers with length N having an absolute difference of adjacent digits equal to K.

Examples:

Input: N = 4, K = 8
Output: 1919, 8080, 9191
Explanation:
The absolute difference between every consecutive digit of each number is 8.
For Example: 8080 (abs(8-0) = 8, abs(0-8) = 8)

Input: N = 2, K = 2
Output: 13, 24, 20, 35, 31, 46, 42, 57, 53, 68, 64, 79, 75, 86, 97
Explanation:
The absolute difference between every consecutive digit of each number is 1.

Approach: The idea is to use Backtracking. Iterate over digits [1, 9] and for each digit from the N-digit number having a difference of absolute digit as K using recursion. Below are the steps:

1. Create a vector ans[] to store all the resulting numbers and recursively iterate from 1 to 9 to generate numbers starting from each digit. Below are the cases:

Base Case: For all integers of a single length, that is, N = 1, add them to ans[].
Recursive Call: If adding digit K to the numbers to one’s digit doesn’t exceed 9, then recursively call by decreasing the N and update num to (10*num + num%10 + K) as shown below:

if(num % 10 + K ? 9) {
recursive_function(10 * num + (num % 10 + K), K, N – 1, and);
}

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

recursive_function(10 * num + num % 10 – K, K, N – 1, ans);

2. After all the above steps print the numbers stored in ans[].

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that recursively finds the
// possible numbers and append into ans
void checkUntil(int num, int K,
                int N, vector<int>& ans)
{
   
    // Base Case
    if (N == 1) 
    {
        ans.push_back(num);
        return;
    }
 
    // Check the sum of last digit and k
    // less than or equal to 9 or not
    if ((num % 10 + K) <= 9)
        checkUntil(10 * num
                       + (num % 10 + K),
                   K, N - 1, ans);
 
    // If k==0, then subtraction and
    // addition does not make any
    // difference
    // Hence, subtraction is skipped
    if (K) {
        if ((num % 10 - K) >= 0)
            checkUntil(10 * num
                           + num % 10 - K,
                       K, N - 1,
                       ans);
    }
}
 
// Function to call checkUntil function
// for every integer from 1 to 9
void check(int K, int N, vector<int>& ans)
{
    // check_util function recursively
    // store all numbers starting from i
    for (int i = 1; i <= 9; i++) {
        checkUntil(i, K, N, ans);
    }
}
 
// Function to print the all numbers
// which  satisfy the conditions
void print(vector<int>& ans)
{
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << ", ";
    }
}
 
// Driver Code
int main()
{
    // Given N and K
    int N = 4, K = 8;
 
    // To store the result
    vector<int> ans;
 
    // Function Call
    check(K, N, ans);
 
    // Print Resultant Numbers
    print(ans);
    return 0;
}

Java

// Java program for 
// the above approach
import java.util.*;
class GFG{
 
    // Function that recursively finds the
    // possible numbers and append into ans
    static void checkUntil(int num, int K, int N,
                           Vector<Integer> ans)
    {
       
        // Base Case
        if (N == 1) 
        {
            ans.add(num);
            return;
        }
 
        // Check the sum of last digit and k
        // less than or equal to 9 or not
        if ((num % 10 + K) <= 9)
            checkUntil(10 * num + (num % 10 + K), 
                       K, N - 1, ans);
 
        // If k==0, then subtraction and
        // addition does not make any
        // difference
        // Hence, subtraction is skipped
        if (K > 0) 
        {
            if ((num % 10 - K) >= 0)
                checkUntil(10 * num + num % 10 - K, 
                           K, N - 1, ans);
        }
    }
 
    // Function to call checkUntil function
    // for every integer from 1 to 9
    static void check(int K, int N, Vector<Integer> ans)
    {
       
        // check_util function recursively
        // store all numbers starting from i
        for (int i = 1; i <= 9; i++) 
        {
            checkUntil(i, K, N, ans);
        }
    }
 
    // Function to print the all numbers
    // which  satisfy the conditions
    static void print(Vector<Integer> ans)
    {
        for (int i = 0; i < ans.size(); i++) 
        {
            System.out.print(ans.get(i) + ", ");
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given N and K
        int N = 4, K = 8;
 
        // To store the result
        Vector<Integer> ans = new Vector<Integer>();;
 
        // Function Call
        check(K, N, ans);
 
        // Print Resultant Numbers
        print(ans);
    }
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program for the above approach
 
# Function that recursively finds the
# possible numbers and append into ans
def checkUntil(num, K, N, ans):
     
    # Base Case
    if (N == 1):
        ans.append(num)
        return
 
    # Check the sum of last digit and k
    # less than or equal to 9 or not
    if ((num % 10 + K) <= 9):
        checkUntil(10 * num +
                 (num % 10 + K), 
                 K, N - 1, ans)
 
    # If k==0, then subtraction and
    # addition does not make any
    # difference
    # Hence, subtraction is skipped
    if (K):
        if ((num % 10 - K) >= 0):
            checkUntil(10 * num +
                      num % 10 - K, 
                     K, N - 1, ans)
     
# Function to call checkUntil function
# for every integer from 1 to 9
def check(K, N, ans):
     
    # check_util function recursively
    # store all numbers starting from i
    for i in range(1, 10):
        checkUntil(i, K, N, ans)
 
# Function to print the all numbers
# which satisfy the conditions
def print_list(ans):
     
    for i in range(len(ans)):
        print(ans[i], end = ", ")
 
# Driver Code
if __name__ == "__main__":
 
    # Given N and K
    N = 4
    K = 8;
 
    # To store the result
    ans = []
 
    # Function call
    check(K, N, ans)
 
    # Print resultant numbers
    print_list(ans)
 
# This code is contributed by chitranayal

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function that recursively finds the
// possible numbers and append into ans
static void checkUntil(int num, int K, int N,
                       List<int> ans)
{
 
    // Base Case
    if (N == 1) 
    {
        ans.Add(num);
        return;
    }
 
    // Check the sum of last digit and k
    // less than or equal to 9 or not
    if ((num % 10 + K) <= 9)
        checkUntil(10 * num + (num % 10 + K), 
                 K, N - 1, ans);
 
    // If k==0, then subtraction and
    // addition does not make any
    // difference
    // Hence, subtraction is skipped
    if (K > 0) 
    {
        if ((num % 10 - K) >= 0)
            checkUntil(10 * num + num % 10 - K, 
                     K, N - 1, ans);
    }
}
 
// Function to call checkUntil function
// for every integer from 1 to 9
static void check(int K, int N, List<int> ans)
{
 
    // check_util function recursively
    // store all numbers starting from i
    for(int i = 1; i <= 9; i++) 
    {
        checkUntil(i, K, N, ans);
    }
}
 
// Function to print the all numbers
// which satisfy the conditions
static void print(List<int> ans)
{
    for(int i = 0; i < ans.Count; i++) 
    {
        Console.Write(ans[i] + ", ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given N and K
    int N = 4, K = 8;
 
    // To store the result
    List<int> ans = new List<int>();;
 
    // Function call
    check(K, N, ans);
 
    // Print Resultant Numbers
    print(ans);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
    // Function that recursively finds the
    // possible numbers and append into ans
    function checkUntil(num, K, N,
                           ans)
    {
         
        // Base Case
        if (N == 1) 
        {
            ans.push(num);
            return;
        }
   
        // Check the sum of last digit and k
        // less than or equal to 9 or not
        if ((num % 10 + K) <= 9)
            checkUntil(10 * num + (num % 10 + K), 
                       K, N - 1, ans);
   
        // If k==0, then subtraction and
        // addition does not make any
        // difference
        // Hence, subtraction is skipped
        if (K > 0) 
        {
            if ((num % 10 - K) >= 0)
                checkUntil(10 * num + num % 10 - K, 
                           K, N - 1, ans);
        }
    }
   
    // Function to call checkUntil function
    // for every integer from 1 to 9
    function check(K, N, ans)
    {
         
        // check_util function recursively
        // store all numbers starting from i
        for (let i = 1; i <= 9; i++) 
        {
            checkUntil(i, K, N, ans);
        }
    }
   
    // Function to print the all numbers
    // which  satisfy the conditions
    function print( ans)
    {
        for (let i = 0; i < ans.length; i++) 
        {
            document.write(ans[i] + ", ");
        }
    }
 
// Driver Code
 
    // Given N and K
        let N = 4, K = 8;
   
        // To store the result
        let ans = []
   
        // Function Call
        check(K, N, ans);
   
        // Print Resultant Numbers
        print(ans);
     
</script>

Output:

1919, 8080, 9191,

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

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!

Generate all N digit numbers having absolute difference as K between adjacent digits

C++

Java

Python3

C#

Javascript

Smarter Retrieval for RAG: Late Chunking with Jina Embeddings v2 and Milvus

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US