DFS and BFS Algorithm to Find Numbers With Same Consecutive Differences

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 except for the number 0 itself. For example, 01 has one leading zero and is invalid, but 0 is valid.

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]

Note:
1 <= N <= 9
0 <= K <= 9

For both DFS and BFS Algorithms (See below), the special cases have to be handled properly. For example, when N=1 one digit, the answer is the array containing single digits from 0 to 9. And when K is 0, the answer is an array of 9 solutions each containing duplicate digits: [111.., 222…, 333…] and so on.

The Bruteforce may not work practically as when N is 9, the search range is O(10^N) which could take a while.

Find Numbers With Same Consecutive Differences by Depth First Search Algorithm

For DFS, we start by putting the first digit (left-most) please note that we don’t try 0 as it is invalid. When we reach the N digits, we push the result.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def numsSameConsecDiff(self, N: int, K: int) -> List[int]:
        if N == 1:
            return list(range(10))
        if K == 0:
            return [str(x)*N for x in range(1, 10)]
        res = []
        for i in range(1, 10):
            self.dfs(N, K, i, res)
        return res
    
    def dfs(self, N, K, i: int, res: List[int]) -> List[int]:
        if N == 1:
            res.append(i)
            return
        c = i % 10
        if c + K < 10:
            self.dfs(N - 1, K, i * 10 + (c + K), res)
        if c - K >= 0:
            self.dfs(N - 1, K, i * 10 + (c - K), res)

class Solution:
    def numsSameConsecDiff(self, N: int, K: int) -> List[int]:
        if N == 1:
            return list(range(10))
        if K == 0:
            return [str(x)*N for x in range(1, 10)]
        res = []
        for i in range(1, 10):
            self.dfs(N, K, i, res)
        return res
    
    def dfs(self, N, K, i: int, res: List[int]) -> List[int]:
        if N == 1:
            res.append(i)
            return
        c = i % 10
        if c + K < 10:
            self.dfs(N - 1, K, i * 10 + (c + K), res)
        if c - K >= 0:
            self.dfs(N - 1, K, i * 10 + (c - K), res)

When we recursively try next digit, we only need to check current digit plus or minus K forms a valid next number. The complexity is O(N*2^N). For space complexity, the usage of Recursion implies O(N), and we use array to store the final answer which could be up to O(9*2^(N-1)). Therefore, the space complexity is O(2^N).

Breadth First Search Algorithm to Find Numbers With Same Consecutive Differences

BFS Algorithm expands the search tree level by level. For example, we finish numbers of 1 digit, and then search all 2-digit numebrs etc.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def numsSameConsecDiff(self, N: int, K: int) -> List[int]:
        if N == 1:
            return list(range(10))
        if K == 0:
            return [str(x)*N for x in range(1, 10)]
        res = []
        Q = list(range(1, 10))
        while len(Q) > 0:
            cur = str(Q.pop(0))
            if len(cur) == N:
                res.append(cur)
            else:
                x = int(cur[-1])
                if x + K < 10:
                    Q.append(cur + str(x + K))
                if x - K >= 0:
                    Q.append(cur + str(x - K))
        return res

class Solution:
    def numsSameConsecDiff(self, N: int, K: int) -> List[int]:
        if N == 1:
            return list(range(10))
        if K == 0:
            return [str(x)*N for x in range(1, 10)]
        res = []
        Q = list(range(1, 10))
        while len(Q) > 0:
            cur = str(Q.pop(0))
            if len(cur) == N:
                res.append(cur)
            else:
                x = int(cur[-1])
                if x + K < 10:
                    Q.append(cur + str(x + K))
                if x - K >= 0:
                    Q.append(cur + str(x - K))
        return res

We use a queue to keep the numbers and we expand the next digits into the queue. The BFS solution has similar time and space complexity.

–EOF (The Ultimate Computing & Technology Blog) —