Numbers With Same Consecutive Differences

Posted: 11 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given two integers, ‘N’ and ‘K’. The task is to return all non-negative integers having ‘N’ digits such that the absolute difference between each consecutive digit is ‘K’.

Example:
Input: N = 2, K = 6
We need to return all two-digit numbers where the absolute difference between each consecutive digit is ‘6’. Note that ‘06’ is not a valid two-digit number. So, the answer is:
Output: [17, 28, 39, 60, 71, 82, 93]
Note:
1. Every number in the answer should not contain leading zeroes. E.g., the number ‘09’ is invalid.

2. You can return the answer in any order.
Input format:
The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

The first and only line of each test case contains two space-separated integers, ‘N’ and ‘K’, denoting the number of digits and the absolute difference between each consecutive digit.
Output format:
For every test case, return an array of integers where each integer has ‘N’ digits, and the absolute difference between each digit is ‘K’. You may return output in any order, but the printed output will be in sorted order.
Note:
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 100
2 <= N <= 9
0 <= K <= 9

Time limit: 1 sec
Approach 1

Let’s first try to find the numbers having ‘4’ as the most significant digit (MSD). We create a tree where each node stores an integer ‘N-i’ and the least significant digit (LSD) of ‘N-i’.  Initially, the tree contains a single node, i.e., the root node with an integer ‘4’ and its LSD ‘4’. We append a new digit to the previous level until we reach 'N' levels. There are two ways to add a new digit to a child node,i.e., ‘LSD of parent node + K’ and ‘LSD of parent node - K’ (Note: For ‘K = 0’ both these values are the same, so there can only be one child). If the LSD of the new node is not between [0, 9], mark this node invalid to produce any child nodes. Following is a partial tree for ‘4’:


 



 

Similarly, solve for numbers having MSD as [1 to 9]. We can do a Breadth-first search (BFS) traversal of the tree to get the leaf nodes. Following are the steps for BFS:

  • Create a queue ‘BFS_QUEUE’ that stores integers. Use this queue for BFS traversal.
  • Push integers from [1 to 9] in ‘BFS_QUEUE’. These are the root nodes for trees with MSD as [1 to 9].
  • Run a loop where ‘i’ ranges from ‘2’ to 'N'. In each iteration, remove the nodes of the previous level from ‘BFS_QUEUE’ and push valid nodes of the next level:
    • ‘SIZE = SIZE_of(BFS_QUEUE)’
    • Run a loop where ‘j’ ranges from ‘1’ to ‘SIZE’:
      • ‘CUR_NUM = BFS_QUEUE.pop()’
      • ‘LSD = CUR_NUM % 10’
      • ‘CUR_NUM *= 10’
      • If ‘LSD + K’ is less than equal to ‘9’:
        • ‘BFS_QUEUE.push(CUR_NUM + LSD + K)’
      • If ‘LSD - K’ is greater than equal to ‘0’ and ‘K’ is not ‘0’:
        • ‘BFS_QUEUE.push(CUR_NUM + LSD - K)’
  • Convert ‘BFS_QUEUE’ into an array and return it as the answer.
Try Problem