Strobogrammatic Number LeetCode Solution

Difficulty Level Easy
Frequently asked in Cisco Facebook Google Microsoft OracleViews 7568

Problem Statement

Strobogrammatic Number LeetCode Solution – Given a string num which represents an integer, return true if num is a strobogrammatic number.

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Example

Test Case 1:

Input:

num =  “69”

Output:

true

Test Case 2:

Input:

num =  “692”

Output:

false

Explanation

i) For the first test case if we rotate “69” by 180 degrees, it’s the same.

ii) For the second test case if we rotate “692” by 180 degrees, it’s not the same number.

Approach

Idea

We need to determine what each digit becomes when rotated by 180 degrees. There are three possibilities for each digit:

  1. it becomes invalid
  2. it stays the same
  3. it becomes a different digit

We’ll consider a digit to be rotatable if, and only if, that digit becomes a valid digit when rotated. If we think carefully, we can identify that 0, 1, 6, 8, 9 are rotatable as only these digits are valid when it is rotated upside down by 180 degrees. So if the number contains any digit other than these, we can easily say that it is not a strobogrammatic number. For other digits, we need to check if their rotation is the same as the number at its counterpart.Strobogrammatic Number LeetCode Solution

Code for Strobogrammatic Number LeetCode Solution

Java Program

class Solution {
    public boolean isStrobogrammatic(String num) {
        Map<Character, Character> map = new HashMap<Character, Character>();
        map.put('6', '9');
        map.put('9', '6');
        map.put('0', '0');
        map.put('1', '1');
        map.put('8', '8');

        int l = 0, r = num.length() - 1;
        while (l <= r) {
            if (!map.containsKey(num.charAt(l))) return false;
            if (map.get(num.charAt(l)) != num.charAt(r))
                return false;
            l++;
            r--;
        }

        return true;
    }
}

C++ Program

class Solution {
public:
    bool isStrobogrammatic(string num) {
        unordered_map<char, char> lut{{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
        for (int l = 0, r = num.size() - 1; l <= r; l++, r--) {
            if (lut.find(num[l]) == lut.end() || lut[num[l]] != num[r]) {
                return false;
            }
        }
        return true;
    }
};

Python Program

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

Complexity Analysis for Strobogrammatic Number LeetCode Solution

Let N be the length of the input string.

Time complexity: O(N)

For each of the N digits in the string, we’re doing a single lookup and comparison.

Space complexity: O(1)

We are only using constant extra space. This is an in-place algorithm.

Reference: https://en.wikipedia.org/wiki/Strobogrammatic_number

Translate »