MEDIUM
DATA STRUCTURES AND ALGORITHMS

# How to Solve Confusing Number

Written By

## 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

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

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

#### 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.