Strobogrammatic Number

A strobogrammatic number is a number that appears the same when rotated 180 degrees. In other words, it looks the same when viewed upside down. To determine if a given string num represents a strobogrammatic number, you can check the following:

1. Define a mapping of digits that are strobogrammatic to their corresponding upside-down counterparts. In this case, the mapping is:

   • ‘0’ -> ‘0’
   • ‘1’ -> ‘1’
   • ‘6’ -> ‘9’
   • ‘8’ -> ‘8’
   • ‘9’ -> ‘6’

2. Iterate through the string num, comparing the characters from the beginning and the end inward, using the mapping to determine if they form a strobogrammatic pair.

3. If you find a character that doesn’t have a strobogrammatic counterpart, or a pair that doesn’t match according to the mapping, return false.

4. If you successfully compare all pairs without contradiction, return true.

Here’s the code that implements these steps:

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

class Solution:
    def isStrobogrammatic(self, num: str) -> bool:
        strobogrammatic_mapping = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}

        start = 0
        end = len(num) - 1

        while start <= end:
            if num[start] not in strobogrammatic_mapping or \
               strobogrammatic_mapping[num[start]] != num[end]:
                return False
            start += 1
            end -= 1

        return True

The time complexity of this function is O(n), where n is the length of the string num. The space complexity is O(1), as we are only using a constant amount of extra space.

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

def isStrobogrammatic(num):
    strobogrammatic_pairs = {"0": "0", "1": "1", "6": "9", "8": "8", "9": "6"}
    i = 0
    j = len(num) - 1
    while i <= j:
        if num[i] not in strobogrammatic_pairs or strobogrammatic_pairs[num[i]] != num[j]:
            return False
        i += 1
        j -= 1
    return True

def main():
    num = "69"
    print(isStrobogrammatic(num))

if __name__ == "__main__":
    main()

This code first initializes a dictionary strobogrammatic_pairs to store the strobogrammatic pairs. Then, it iterates over the num string, comparing the current character to the character at the opposite end of the string. If the characters are not equal or if the current character is not in the strobogrammatic_pairs dictionary, then the code returns False. Otherwise, the code increments i and decrements j and continues iterating. Finally, the code returns True if the loop terminates normally.

To run the code, you can save it as a Python file and then run it from the command line. For example, if you save the code as is_strobogrammatic_number.py, you can run it by typing the following command into the command line:

python is_strobogrammatic_number.py

This will print True to the console.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def isStrobogrammatic(self, num: str) -> bool:
        strobogrammatic_pairs = {"0": "0", "1": "1", "6": "9", "8": "8", "9": "6"}
        i = 0
        j = len(num) - 1
        while i <= j:
            if num[i] not in strobogrammatic_pairs or strobogrammatic_pairs[num[i]] != num[j]:
                return False
            i += 1
            j -= 1
        return True

The values for the strobogrammatic_pairs hash table were chosen based on the definition of a strobogrammatic number. A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). The numbers 0, 1, 6, 8, and 9 are all mirror images of themselves, so they are all strobogrammatic. The pairs 6 and 9 are also mirror images of each other, so they are also strobogrammatic.

The hash table stores the strobogrammatic pairs as key-value pairs. The key is the digit that appears in the original number, and the value is the digit that appears in the rotated number. For example, the key “0” maps to the value “0”, because 0 is a mirror image of itself. The key “6” maps to the value “9”, because 6 and 9 are mirror images of each other.

The hash table can be used to quickly check if a number is strobogrammatic. For example, to check if the number 69 is strobogrammatic, you would look up the key “6” in the hash table. If the value associated with the key is “9”, then the number is strobogrammatic. Otherwise, the number is not strobogrammatic.

I think ‘2’ and ‘5’ can also be looked as “Strobogrammatic Number” ‘1’ and ‘8’ are not even exactly Strobogrammatic if you want it to look perfectly rotationally symmetric . Wikipedia thinks ‘2’ is Strobogrammatic.

You are right, ‘2’ and ‘5’ can also be considered strobogrammatic numbers. The definition of a strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). ‘2’ and ‘5’ both satisfy this definition, as they are rotationally symmetric.

However, the definition of a strobogrammatic number is not always consistent. Some sources only consider the numbers 0, 1, 6, 8, and 9 to be strobogrammatic, while others include 2 and 5 as well. Ultimately, the definition of a strobogrammatic number is up to the individual or organization that is using the term.

In the code that I provided, I only considered the numbers 0, 1, 6, 8, and 9 to be strobogrammatic. However, it would be easy to modify the code to include 2 and 5 as well.

For those annoyed with the lack of clarity, the strobogrammatic numbers are 0, 1, and 8 on their own. The pair of 6 and 9 are counted.

I’m using a digital clock, and when I turn 629 upside down, it’s the same. Both 2 and 5 are strobogrammatic with themselves 555 = 555 2605092 = 2605092

Assume we are “rotating” on the z-axis And digital numbers are close enough

I did a test of 629 and got “expected false”

You are correct, if you are rotating a digital clock 180 degrees on the z-axis, then 629 would be a strobogrammatic number. The code that I provided only considers the numbers 0, 1, 6, 8, and 9 to be strobogrammatic, so it would return False for 629.

However, it would be easy to modify the code to include 2 and 5 as well. The following code would do this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def isStrobogrammatic(num):
    strobogrammatic_pairs = {"0": "0", "1": "1", "2": "2", "5": "5", "6": "9", "8": "8", "9": "6"}
    i = 0
    j = len(num) - 1
    while i <= j:
        if num[i] not in strobogrammatic_pairs or strobogrammatic_pairs[num[i]] != num[j]:
            return False
        i += 1
        j -= 1
    return True

This code would return True for 629, as well as for other numbers that are strobogrammatic when rotated 180 degrees on the z-axis.

How is “1” or “11” strobo, but “10” or “18” are not?

The definition of a strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). 1 and 11 are strobogrammatic because they are mirror images of themselves. 10 and 18 are not strobogrammatic because they are not mirror images of themselves.

Here is a table showing the strobogrammatic numbers:

Number | Strobogrammatic?
------- | --------
0 | Yes
1 | Yes
2 | Yes (if you consider 2 and 5 to be strobogrammatic)
5 | Yes (if you consider 2 and 5 to be strobogrammatic)
6 | Yes
8 | Yes
9 | Yes
10 | No
11 | Yes
12 | No
15 | No
16 | No
18 | No

The solution seems to be similar to palindrome string problem. Is that correct? The structure of the problem is the same as that problem?

As you can see, the strobogrammatic numbers are all either single-digit numbers or pairs of digits that are mirror images of each other.

Yes, the solution to the strobogrammatic number problem is similar to the solution to the palindrome string problem. Both problems involve checking if a string is the same when reversed. The main difference between the two problems is that the strobogrammatic number problem only allows certain digits to appear in the string.

The structure of the two problems is also similar. Both problems involve iterating over the string, comparing each character to the character at the opposite end of the string. If the characters are not equal, then the string is not a palindrome or a strobogrammatic number.

Here is a table showing the similarities and differences between the two problems: