Confusing Number Introduction
Confusing Number Introduction
The Confusing Number problem presents us with a problem with real-life implications. The setting of an auction room is one that is easy to visualize. The problem asks us to write a function to identify all numbers that could create confusion when accidentally held upside down, hence "confusable numbers". These numbers when upside down would turn into a different unique number. This problem requires careful consideration and logical thought into a variety of edge cases such as numbers ending in zero or numbers that when flipped stay the same.
Confusing Number Problem
Confusing Number Problem
Consider an auction: there are BIDDERS in the audience. Each BIDDER is given a paddle with a unique number (e.g.: 57). At the front, there is an ORGANIZER. When a BIDDER raises their paddle, the ORGANIZER sees it and recognizes the number. For instance, a BIDDER might raise paddle #78, and the ORGANIZER recognizes the number 78.
Sometimes, however, a BIDDER accidentally holds the paddle upside down. For instance, a BIDDER with the number 68 holds it upside down, showing the number 89. The ORGANIZER assumes it's 89, which is a mistake. We'll call any number that--when turned upside down--is a different, valid number, a CONFUSABLE number.
Write a function that, given a room with 800 BIDDERS, identifies all the confusable numbers.
Confusing Number Solutions
Confusing Number Solutions
To solve this problem, we iterate through the range of numbers from 1 to 800, representing the bidders in the room. For each number, we check if it is a confusable number when flipped upside down.
We start by creating a flip map that maps each valid digit to its flipped counterpart. Then, for each number in the range, we iterate through its digits and construct the flipped number by replacing each digit with its flipped counterpart from the flip map. After obtaining the flipped number, we perform additional checks to determine if it is a confusable number. First, we check if the flipped number is different from the original number. If the flipped number is the same as the original number, for example the number "69", then it's not confusable, so we move on to the next number.
Next, we check if the flipped number has a leading zero which would visually indicate the number is upside down and isn't a cause for confusion. If the last digit of the flipped number is zero, it would be an invalid number and not confusable. In such cases, we skip the number. Additionally, we consider specific cases for three-digit numbers. We exclude numbers ending in zero, as they are not confusable when flipped upside down. Furthermore, we exclude numbers where the first digit is 6, the middle digit is 1, 8, or 0, and the last digit is 9. Similarly, we exclude numbers where the first digit is 9, the middle digit is 1, 8, or 0, and the last digit is 6. These combinations result in the same number when flipped, so they are not considered confusable.
Finally, we collect all the valid confusable numbers and return them as the result.
def find_confusable_numbers():
flip_map = {"0": "0", "1": "1", "6": "9", "8": "8", "9": "6"}
def isConfusable(num):
flipped = ""
for digit in str(num):
if digit not in flip_map:
return False
flipped += flip_map[digit]
# Check if the flipped number is different from the original number
if num != int(flipped):
# Check if the flipped number ends in zero, which would make it invalid
if flipped[-1] == "0":
return False
# Check if the first digit is 6 and the last digit is 9, or vice versa
if (flipped[0] == "6" and flipped[-1] == "9") or (flipped[0] == "9" and flipped[-1] == "6"):
return False
# Check if the number is a three-digit number and satisfies the specific conditions
if len(str(num)) == 3 and (num % 10 == 0 or num % 10 == 8 or num % 10 == 6):
return False
return True
return False
confusables = []
for num in range(1, 800):
if isConfusable(num):
confusables.append(num)
return confusables
confusables = find_confusable_numbers()
print(confusables)1def find_confusable_numbers():
2 flip_map = {"0": "0", "1": "1", "6": "9", "8": "8", "9": "6"}
3
4 def isConfusable(num):
5 flipped = ""
6 for digit in str(num):
7 if digit not in flip_map:
8 return False
9 flipped += flip_map[digit]
10
11 # Check if the flipped number is different from the original number
12 if num != int(flipped):
13 # Check if the flipped number ends in zero, which would make it invalid
14 if flipped[-1] == "0":
15 return False
16 # Check if the first digit is 6 and the last digit is 9, or vice versa
17 if (flipped[0] == "6" and flipped[-1] == "9") or (flipped[0] == "9" and flipped[-1] == "6"):
18 return False
19 # Check if the number is a three-digit number and satisfies the specific conditions
20 if len(str(num)) == 3 and (num % 10 == 0 or num % 10 == 8 or num % 10 == 6):
21 return False
22 return True
23
24 return False
25
26 confusables = []
27 for num in range(1, 800):
28 if isConfusable(num):
29 confusables.append(num)
30
31 return confusables
32
33confusables = find_confusable_numbers()
34print(confusables)Time/Space Complexity Analysis
- Time Complexity: O(N*M), where N is the range of numbers and M is the number of digits in each number.
- Space Complexity: O(1), as we only use a constant amount of extra space to store the flip map, variables, and the list of confusable numbers.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
