[Facebook Question] Strobogrammatic Number

Problem: Given a string num which represents an integer, return true if num is a strobogrammatic number. 

A strobogrammatic number is a number whose numeral is rotationally symmetric, so that it appears the same when rotated 180 degrees. In other words, the numeral looks the same right-side up and upside down

Example:

Input: num = "9966"
Output: true

Input: num = "1001"
Output: true

Approach: We can simply maintain a hash table say Rotation_Map with key as number and value as the number which you will get after rotating it by 180 degree. Here are the pairs -

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

Now we will reverse the given string and call it say rev_string. Now for i = 0 to length - 1 we check if num[i] exist in the rotation table and if rev_string[i] is equal to Rotation_Map[num[i]]. At any point if we see this condition is not true then we can safely return false.

In the end if we find every character in input string satisfy the condition, we return true.

 

Implementation in C#:

        public static bool IsStrobogrammatic(string num)

        {

            Dictionary<char, char> rotationMap = new Dictionary<char, char>();

            rotationMap['0'] = '0';

            rotationMap['1'] = '1';

            rotationMap['6'] = '9';

            rotationMap['8'] = '8';

            rotationMap['9'] = '6';

            char[] revArr = num.ToCharArray();

            Array.Reverse(revArr);

            for (int i = 0; i < revArr.Length; ++i)

            {

                if (rotationMap.ContainsKey(num[i]) )

                {

                    if (rotationMap[num[i]] != revArr[i])

                    {

                        return false;

                    }

                }

                else if (num[i] != revArr[i])

                {

                    return false;

                }

            }

            return true;

        }

Complexity: O(n)