DFS and BFS Algorithm to Find Numbers With Same Consecutive Diff

  • Time:2020-09-07 12:13:31
  • Class:Weblog
  • Read:26

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) —

Recommend:
U.S. Congress passes massive military spending bill despite crit
Progress in China-U.S. audit oversight cooperation welcome: CSRC
UN officials call for building consensus on biodiversity bluepri
Chinese mainland reports 2,091 new local confirmed COVID-19 case
Research sheds light on rice's natural defenses
NDRC assures recovery to continue next year
US draws sharp criticism from WTO members
Yearly meeting outlines 2023 growth plans
One quarter of biodiversity facing extinction by 2100: report
Distributed PV power generation injects vitality into China's gr
Share:Facebook Twitter
Comment list
Comment add