Numbers With Same Consecutive Differences

Posted: 13 Mar, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

You are given two integers ‘N’ and ‘K’. You need to return all non-negative integers of length N, such that the absolute difference between every two consecutive digits is ‘K’.

Note:
 Note that leading zeros of a number are not counted as digits. For example, 010, has two digits and not three.
For example :
Given N = 2, K = 4, so the list of numbers of length 2, having difference between digits 4 are : [15, 26, 37, 40, 48, 51, 59, 62, 73, 84, 95] 
Input Format:
The first line contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first and the only line of each test case contains two space-separated integers, ‘N’ and ‘K’, denoting the length of integer and difference between consecutive digits.
Output Format:
For each test case, you need to print all the possible non-negative integers of length ‘N’, having a difference ‘K’ between two consecutive digits.

Print the possible numbers in sorted order.

Print the output of each test case in a separate line.
Note:
You don’t need to print anything; It has already been taken care of.
Constraints:
1 <= T <= 10
2 <= N <= 9
0 <= K <= 9

Time limit: 1 sec
Approach 1

The basic idea behind solving this question is to create a digit combination that could help us in creating a defined pattern. Let us start by taking an example: Let N = 2, K = 4.

 

Start by taking digit by digit. Let us start with 1, so the next digit will be 5, making the number = 15, This will be the same for finding the numbers, 26, 37. Now, if we take the digit 4, then there are two options for the next digit, 0 or 8, making two numbers 40 and 48. This will, move forward to getting rest numbers. 

 

This process can be illustrated using the following tree:

Here, every node denotes the digit that we pick and each level is the place for the digit.

 

So, we now need to traverse through this created tree and each traversal from the root to the leaf will be each answer.

 

For the first approach, we will start by depth first traversal. We simply create a recursive function let’s say DFS(N, num), where ‘N’ is the level of the created tree, and “num” will be the current number. The function will return the combinations of the remaining numbers, starting from the current number. 

 

For example:

N = 3 K = 4,

We will have the following tree:

The recursive function DFS(2, 1) will return 15 and further DFS(1, 15), will return all combinations of answers, that is 151 and 159.

 

Algorithm:

 

  • The base case would be when N = 0, that is there are no more digits to add in the number:
    • Simply return the currently formed number
  • For the rest of the digits, we will have two cases:
    • Digit + Difference
    • Digit - Difference
    • If any of the above values becomes negative or becomes more than 9 that is if any of the above values don’t lie in the range [0, 9], then it is rejected.
    • Else if it lies in the range, we continue the process and recursively call again, until we reach the maximum number of digits given.
  • Return the number formed.

 

We call the above recursive function for the complete range starting from 1 to 9, we do not start with 0 as 0 followed by any number will not be a valid answer.

Try Problem