Last Updated: 14 Apr, 2021
Strobogrammatic Number
Moderate
Asked in company
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.
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
Approaches
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.
- 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'.
- 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.