Numbers With Same Consecutive Differences

Hard
0/120
Average time to solve is 50m
profile
Contributed by
15 upvotes
Asked in companies
AppleAdobeFacebook

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]
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2 4
3 0
Sample Output 1:
15 26 37 40 48 51 59 62 73 84 95
111 222 333 444 555 666 777 888 999
Explanation For Sample Input 1:
In the first test case, 

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] 


In the second test case, 

N = 3, K = 0, so the list of numbers of length 3, having difference between digits 0 are : [111, 222, 333, 444, 555, 666, 777, 888, 999]
Sample Input 2:
2
2 0
2 9
Sample Output 2:
11 22 33 44 55 66 77 88 99
90
Hint

Can you think of Depth First Traversal?

Approaches (2)
Depth First Traversal

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.

Time Complexity

O(2 ^ N), where N is the length of the number formed.

 

In the worst case the tree formed with depth = ‘N - 1’, will have a total number of  2 ^ N nodes, traversing them in depth first manner. Hence the overall time complexity of this approach is O(2 ^ N).

Space Complexity

O(2 ^ N), where N is the length of the number formed.

 

The space required for recursive stack is O(N), also the space required to store the result is O(9 * (2 ^ (N - 1))). Adding the two complexities, the overall complexity of this approach is O(2 ^ N).

Code Solution
(100% EXP penalty)
Numbers With Same Consecutive Differences
Full screen
Console