Numbers With Same Consecutive Differences

PROBLEM STATEMENT

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

Approach 2

The other way of traversing through the tree would be by breadth first approach. In this case, instead of building the solution one by one, we will create solutions level by level.

For example:

N = 3, K = 6

The numbers formed in the final level will be our solution.

Algorithm:

Create a queue to store the numbers in each level.
Now we iterate through the levels and using another nested loop, simply make changes in the elements of each level.
We will apply the same logic as we did in the DFS approach:
- 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,
    - Instead of recursively calling the next number, we will simply add the number in the queue for the next level.
Return the numbers stored in the final level.

Try Problem