Teaching Kids Programming – Contiguously Increasing Numbers (Depth First Search and Breadth First Search Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given two integers start and end, return a sorted list of integers such that every number e is between start ≤ e ≤ end and the digits of e are contiguously increasing. For example, 2345 is contiguously increasing while 135 and 321 are not.

Constraints
0 ≤ start ≤ end < 2 ** 31
Example 1
Input
start = 0
end = 100
Output
[1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 23, 34, 45, 56, 67, 78, 89]

Do BFS from numbers starting from 1 to 9. Add next number according to the last digit. If the number is in the range then add it to our result set.

Say a number 12. We can add 3 to make it 123. Similarly add 4 to get 1234.

Count Contiguously Increasing Numbers

There are total 45 Contiguously Increasing Numbers – because each number will eventually stop at number 9. There are 9 numbers starting at digit 1 e.g. 1, 12, 123, … 123456789. And there are 8 numbers starting at digit 2 and so on (Teaching Kids Programming – Compute the Number of Sublists by Combination in Math).

We can bruteforce all these numbers by picking the sublist in the string “123456789”:

1
2
3
4
5
6
7
8
9
10

class Solution:
    def solve(self, start, end):
        s = "123456789"
        a = []
        for i in range(9):
            for j in range(i + 1, 10):
                x = int(s[i:j])
                if start <= x <= end:
                    a += (x,)
        return sorted(a)

class Solution:
    def solve(self, start, end):
        s = "123456789"
        a = []
        for i in range(9):
            for j in range(i + 1, 10):
                x = int(s[i:j])
                if start <= x <= end:
                    a += (x,)
        return sorted(a)

The time and space complexity is O(45) which is O(1) constant.

Contiguously Increasing Numbers via Depth First Search Algorithm

We can start searching the numbers (via Recursive Depth First Search Algorithm DFS) by placing the first number which could be 9 choices. We will keep adding digits as long as current digit is still lower than the upperbound and also the last digit is not 9.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def solve(self, start, end):
        ans = []
        def dfs(n):
            nonlocal ans
            if start <= n <= end:
                ans += [n]
            if n > end:
                return
            last = n % 10
            if last != 9:
                dfs(n * 10 + last + 1)
        for i in range(1, 10):
            dfs(i)
        return sorted(ans)

class Solution:
    def solve(self, start, end):
        ans = []
        def dfs(n):
            nonlocal ans
            if start <= n <= end:
                ans += [n]
            if n > end:
                return
            last = n % 10
            if last != 9:
                dfs(n * 10 + last + 1)
        for i in range(1, 10):
            dfs(i)
        return sorted(ans)

Same constant time/space complexity.

Contiguously Increasing Numbers via Breadth First Search Algorithm

We can also perform the Breadth First Search (BFS) Algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def solve(self, start, end):
        q = deque()
        for i in range(1, 10):
            q.append(i)
        ans = []
        while q:
            cur = q.popleft()
            if start <= cur <= end:
                ans += (cur,)
            if cur < end:
                last = cur % 10
                if last != 9:
                    q.append(cur * 10 + last + 1)
        return ans

class Solution:
    def solve(self, start, end):
        q = deque()
        for i in range(1, 10):
            q.append(i)
        ans = []
        while q:
            cur = q.popleft()
            if start <= cur <= end:
                ans += (cur,)
            if cur < end:
                last = cur % 10
                if last != 9:
                    q.append(cur * 10 + last + 1)
        return ans

We use a queue to implement the Breadth First Search and add the digits in a similar way (still smaller than the upperbound and last digit is not 9).

–EOF (The Ultimate Computing & Technology Blog) —