Approach 1: Brute Force
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.
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
Time Complexity: .
Space Complexity: .
Analysis written by: @awice.