Strobogrammatic Number

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
34 upvotes
Asked in company
Google inc

Problem statement

Given a string ‘N’ that represents a number, you need to check if the given number is a strobogrammatic number or not.

A strobogrammatic number is a number that looks the same when rotated by 180.

In other words, a number that on rotating right side up and upside down appears the same is a strobogrammatic number.

For Example: 
‘986’ is a strobogrammatic number because on rotating ‘986’ by 180, ‘986’ will be obtained.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains a string denoting ‘N’.
Output Format: 
For each test case, return “True”, if the given number is a strobogrammatic number, otherwise return “False”.
Note: 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 50
0 <= N <= 10^5

Time limit: 1 sec
Sample Input 1:
2
191
8008
Sample Output 1:
False
True
Explanation Of Sample Input 1:
Test Case 1: On rotating ‘191’ by 180, ‘161’ will be formed. So ‘191’ is not a strobogrammatic number.


Test Case 2: On rotating ‘8008’, ‘8008’ will be obtained. So ‘8008’ is a strobogrammatic number.

Sample Input 2:
2
8888
543
Sample Output 2:
True
False
Hint

Try to figure out the digits which on rotating upside down, generates a valid digit.

Approaches (1)
Brute-Force

Out of all the 10 digits, 0,1,6,8,9 will give a valid digit when rotated upside down(top part turned to bottom).

 

After rotating upside down digits will be-

 

0 -> 0

1 -> 1

6 -> 9

8 -> 8

9 -> 6

 

We will use two pointers, 'START' and 'END', pointing to the number’s starting and ending digit.

 

 By rotating the number right side up, the digit at 'START' will be replaced by the digit at 'END'. Now, if the digit at 'START' is a digit other than (0,1,6,8,9), then the number can never be a strobogrammatic number.

 

Otherwise, we will find if the digit at 'START'  on rotating upside down appears the same as the digit at 'END'.

 

We will check this for all values until 'Start' < ‘END’. 

If for all values of 'START', digit at 'START' on rotating upside down appears as digit at 'END', then the given number is a strobogrammatic number.

 

Algorithm:

 

  • Store length of string ‘N’ in a variable ‘LEN’.
  • Initialize two variables, 'START' and ‘END,’ initially storing the index of the first and last digit of the number.
  • Run a loop until 'Start' < END.
    • If the digit at 'Start' and END is any of these combinations [ 0, 0 ], [ 1,1 ], [ 6, 9 ], [ 8, 8 ] or [ 9, 6 ] then it can be said that the digit at 'START' on rotating upside down appears the same as the digit at 'END'.
      • Increment 'START' by ‘1’ and decrement 'END' by ‘1’ to check for the next pair of digits.
    • Otherwise, return false. It denotes that the given number is not a strobogrammatic number.
  • Check for digit at 'START' and 'END' (to check middle digit). If rotating digit at 'START' appears the same as the digit at 'END' return true. Otherwise, return false.
Time Complexity

O(N), where ‘N’ is the length of the string.

 

We are iterating through half of the digits of the string. So the time complexity is O(|N|).

Space Complexity

O(1),

 

No extra space is used. So the space complexity is O(1).

Code Solution
(100% EXP penalty)
Strobogrammatic Number
Full screen
Console