Solution


Approach 1: Brute Force

Intuition

Let's try to write some number in the answer digit by digit.

For each digit except the first, there are at most 2 choices for that digit. This means that there are at most possible 9 digit numbers, for example. This is small enough to brute force.

Algorithm

An digit number is just an digit number with a final digit added. If the digit number ends in a digit , then the digit number will end in or (provided these are digits in the range ). We store these numbers in a Set structure to avoid duplicates.

Also, we should be careful about leading zeroes -- only 1 digit numbers will start with 0.

Complexity Analysis

  • Time Complexity: .

  • Space Complexity: .


Analysis written by: @awice.