967. Numbers With Same Consecutive Differences

Problem #967 (Numbers With Same Consecutive Differences | Backtracking, Breadth First Search)

Return all non-negative integers of length n such that the absolute difference between every two consecutive digits is k.

Note that every number in the answer must not have leading zeros. For example, 01 has one leading zero and is invalid.

You may return the answer in any order.

Example 1

Input:

n = 3, k = 7

Output:

[181,292,707,818,929]

Explanation:

Note that 070 is not a valid number, because it has leading zeroes.

Example 2

Input:

n = 2, k = 1

Output:

[10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Constraints

• 2 <= n <= 9
• 0 <= k <= 9

Solutions

Basic Idea

The problem asks us to return a list of values(integers) in which each value is n digits and the absolute difference of each two consecutive digits is k. If n is 3, then the values inside the Queue should be 3 digits.

Sample

n = 3, k = 4

• This means that the numbers in the list should have a length of 3 and each two consecutive digits of a number has an absolute difference of 4.

Output: [151,159,262,373,404,484,515,595,626,737,840,848,951,959]

• Notice that some number has consecutive digits that has the same first digit but different second digit. Numbers such as:

  • [151,159]
  • [404,484]
  • [840,848]
  • [951,959]

• From these numbers we can conclude that two numbers with same first digit but different second digit can have the same absolute difference. Pairs such as(where k = 4):

  • (5, 1) and (5, 9)
  • (4, 0) and (4, 8)

• To find whether the first digit can be paired to 2 different second digits, it must satisfy these conditions:

  1. k > 0 and x - k >= 0
  2. x + k < 10

NOTE: If it only satisfies one then it only has 1 pair.

Example:

k = 4
x = 5, this refers to the first digit

1. k > 0 and x - k >= 0
    5 - 4 >= 0, true
    5 - 4 = 1, a pair
    
    | 5 - 1 | = 4, absolute difference = k
    
    Therefore, 1 is a pair of 5.

2. x + k < 10
    5 + 4 < 10, true
    5 + 4 = 9, a pair
    
    | 5 - 9 | = 4, absolute difference = k
    
    Therefore, 9 is a pair of 5.

Breadth First Search(Iterative)

The basic idea in an iterative BFS is to create a List where we will store the n digit numbers. We will use a for loop to loop from 1 - 9 which corresponds to the beginning of a number(num). For each iteration, we will create a Queue where we will first add(i) then process it inside a while loop. Inside the while loop we will determine all possible combination of numbers until our number reaches n digits. When the number satisfies all condition and rule, add it to te List.

Code Structure

vector<int> list;
min = pow(10, n - 1);

• Create a list where we will store our results. Our min is basically the minimum value of the values inside the list.

for(int i = 0; i < 10; i++){
    queue<int> q;
    q.push(i);
}

• We will iterate from 1 - 9, these numbers are assigned to i which corresponds to the beginning of our number. We will then create a Queue where we will store the numbers, where for each number, we will determine the next digit where the absolute difference of the next digit and preceded digit is k. By default, the Queue first contains the first digit of our number which is i.

---

for(int i = 0; i < 10; i++){
    queue<int> q;
    q.push(i);
    while (!q.empty()) {
        int num = q.front();
        q.pop();
    }
}

• for each iteration, we will execute a while loop until our Queue is empty. Inside the while loop, we will get the first value in our Queue and assign it to num and remove it from our Queue.

---

for(int i = 0; i < 10; i++){
    queue<int> q;
    q.push(i);
    while (!q.empty()) {
        int num = q.front();
        q.pop();
        if(num >= min){
            list.push_back(num);
            continue;
        }
        int x = num % 10;
        if (k > 0 && x - k >= 0)
            q.push(num * 10 + x - k)
        if (x + k < 10)
            q.push(num * 10 + x + k)
    }

• Once we pop a number from our Queue and assign to num, we will check whether that num is greater than or equal to our min, if it is, then add it to our List and continue. If not, then get the last digit of our num then find its pair/s of number in which their absolute difference is k. x should satisfy these conditions:

  1. k > 0 and x - k >= 0
  2. x + k < 10

• If only one of the conditions is satisfied then x only has one pair.

• Add the resulting number to our Queue when that pair of x is added as a last digit of our number.

  num = num * 10 + {pair}, pair can either be x + k = pair or x - k = pair or both depending on the conditions satisfied by x.

• Once the new num is added to our Queue, our while loop still hold thus continue executing its statements for each values in the Queue until all values are greater than min, which will then satisfy the if condition where we will add the values to our list and empty our Queue. Once the Queue is empty, exit the while loop and increment i thus beginning another iteration for a number starting at 2, repeat loop until i = 9.

---

• Queue after getting the next digit of 1.

---

• Queue is popped, num = 15.

---

• num is less than min thus find its next digit.
• There are two digits that can be paired with the last digit of num. Add the resulting numbers to the Queue.

---

• Queue now has two values.

---

• 151 is popped and assigned to num.

---

• 151 is greater than min thus add it to the List.

---

• Queue has one value.
• List has one value.

---

• 159 is popped and assigned to num.

---

• 159 is greater than min thus add it to the List.

---

• Queue is empty.
• List has two values.

---

• Queue is empty thus exit the while loop.

---

• do another iteration, number begins at 2.

---

Keep doing this until i = 9.

---

• Final List

```cpp return list; ``` - Once we exit the ***for loop***, return our `List` which should contain all values that are `n` digits and for each ***two consecutive digits***, they have an ***absolute difference*** of `k`.

Code

• Java

class Solution {
    public int[] numsSameConsecDiff(int n, int k) {
        if(n == 1) return new int[]{k};
        List<Integer> list = new ArrayList<Integer>();
        int min = (int) Math.pow(10, n - 1);
        for(int i = 1; i < 10; i++){
            Queue<Integer> q = new LinkedList<Integer>();
            q.add(i);
            while(!q.isEmpty()){
                int num = q.poll();
                if (num >= min){
                    list.add(num);
                    continue;
                }
                int x = num%10;
                if(k > 0 && x - k >= 0)
                    q.add(num * 10 + x - k);
                if(x + k < 10)
                    q.add(num * 10 + x + k);
            }
        }
        return list.stream()
                   .mapToInt(i -> i)
                   .toArray();
    }
}

• C++

class Solution {
public:
    vector<int> numsSameConsecDiff(int n, int k) {
        if(n == 1) return vector<int>{k};
        vector<int> list;
        int min = pow(10, n - 1);
        for(int i = 1; i < 10; i++){
            queue<int> q;
            q.push(i);
            while(!q.empty()){
                int num = q.front();
                q.pop();
                if(num >= min){
                    list.push_back(num);
                    continue;
                }
                int x = num % 10;
                if(k > 0 && x - k >= 0)
                    q.push(num * 10 + x - k);
                if(x + k < 10)
                    q.push(num * 10 + x + k);
            }
        }
        return list;
    }
};

• Python

class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        list = []
        min = pow(10, n - 1)
        for i in range (1, 10):
            q = [i]
            while len(q):
                num = q.pop(0)
                if num >= min:
                    list.append(num)
                    continue
                x = num % 10
                if k > 0 and x - k >= 0:
                    q.append(num * 10 + x - k)
                if x + k < 10:
                    q.append(num * 10 + x + k)
        return list

Complexity

• Time: O(n)
• Space: O(2^n)