Java Program to Generate All N Digit Numbers Having Absolute Difference as K Between Adjacent Digits

It is always fun to generate sequences of numbers that fit certain rules and to constain the difference in numbers in adjacent positions will make this problem even more intriguing. In this article, we will understand how to generate all N-digit numbers such that the difference between any two consecutive digit of a number is exactly K. In the next section we will elaborate on the rationale for this approach and specify a recursive solution in Java.

Problem Statement

Given integers N and K:

Generate all N-digit numbers such that the difference between any two consecutive digits is K.

For example, if N=3 and K=2 could in fact be 131, 242, … where any two consecutive digits are apart by only 2 at most.

Approach to the Solution

Define the Constraints:

• Each number generated must be N digits long.
• For every two adjacent digits d1 and d2 in the number, ∣d1−d2∣=K.
• To avoid leading zeros in N-digit numbers, it is mandatory to have the first digit as shall than zero.

Recursive Backtracking:

• Use a recursive function to build each valid NNN-digit number digit by digit.
• It is starting with any digit between 1 to 9 (no leading zeroes) and then adding numbers so that absolute difference between two adjacent numbers is K.

Exploring the Next Digit:

• For a current digit d, the next digit can be d+K or d−k, only if they are between 0 to 9 inclusive.
• Keep adding on the number until you get N digits, add it to the result list.

File Name: NumberGenerator.java

Output:

 N-digit numbers with absolute difference K between adjacent digits: 135 131 246 242 202 357 353 313 468 464 424 420 579 575 535 531 686 646 642 797 757 753 868 864 979 975 

Explanation

Main Generation Method (generateNumbers):

• This one sets up the generational process. It begins with each digit of 1 to 9 where it calls the recursive helper function generateRecursive to build all numbers that will form the resultant string with above mentioned conditions.

Recursive Helper Method (generateRecursive):

• Base Case: If the number length reaches N, then added to the results list.
• Recursive Case: What is more, for each valid digit in the current position, the function:
  
  • Brings another digit to the digit in the parentheses and increases the number of digits in the parentheses.
  • Reaches out to itself to add the next digit in building the number being passed on to it as the argument.
• The next possible digits can be found by adding and subtracting K from the current digit.
• Avoiding Duplicate Numbers: When K is 0, the adding and subtracting K from the current digit gives the same result therefore it is sufficient to have only one case against the numbers to be repeated.

Conclusion

Using recursion to generate N-digit numbers that have an absolute difference 𝐾 is simple and beautiful algorithm that uses the concept of backtracking. Like said before this solution is not only adequate in handling recursion related problems but is also viable in problems that demands specific pattern of digits.

That is the pattern similar to what was described in the text and using this recursive structure you can produce similar patterns, and in fact, the same code can be used for other constraints, for example, numbers whose differences are relatively prime or numbers satisfying certain sum conditions.