Special Numbers

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in companies
OYOSAP LabsPayPal

Problem statement

You are given an integer, ‘MAXVAL’. Your task is to determine the total number of special numbers present in the range, 1 to ‘MAXVAL’.

Note: 
A special number is a number, which when rotated 180 degrees, resembles some other number in the same range. Every digit of a special number must be a valid digit.

The digits, 0,1,6,8,9, when rotated 180 degrees, become 0,1,9,8,6 respectively. While the digits, 2,3,4,5,7, when rotated do not become any valid digit.
For example: 
‘8196’, when rotated 180 degrees, will become ‘9618’. We can observe that all the digits of this number are valid. So, this is a special number.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains a single integer, ‘MAXVAL’.
Output Format: 
For each test case, print a single integer, denoting the total number of special numbers in the range, 1 to ‘MAXVAL’.

Output for each test case will be printed in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= MAXVAL < 10^4

Time Limit: 1sec
Sample Input 1:
1
10
Sample Output 1:
2
Explanation For Sample Input 1:
There are only two special numbers in the range from ‘1’ to ‘10’. These two numbers are ‘6’ and ‘9’. 

We can not consider ‘1’ and ‘8’ because these numbers, when rotated, give the same number back so they can not be termed as special numbers. ‘10’ can also not be considered as a special number because, after rotation, it becomes ‘01’. Although, the numerical value of ‘01’ is also ‘1’, the representation of ‘01’ is different from ‘1’. 

Hence, there are only two special numbers in this range.
Sample Input 2:
1
16
Sample Output 2:
2
Hint

Check for all numbers in the range independently

Approaches (2)
Check all numbers independently

The approach is to loop through all the numbers in the given range one by one and check whether this number is a special number or not. We can check if a number is special or not, by rotating it. This can be achieved by reversing the string representation of the number and thereafter, replacing every ‘6’ by ‘9’ and vice versa. 

 

Steps:

 

  • Initialize a variable, say count = 0. This will store the total count of special numbers in the given range.
  • Now, run a loop from num = 1 to num <= maxVal, and do:
    • Define a variable, say numString to store the string representation of num.
    • Now, define a boolean variable, say specialNum, and set it to true.
    • Now, check for every character, a, in numString.
      • If a is either 2, 3, 4, 5, 7, make specialNum = false.
    • Now, if specialNum = true, do:
      • Store the length of numString in len.
      • Run a loop from i = 0 to i < len / 2, and swap characters at numString[i] and numString[len - 1 - i].
      • Run a loop from i = 0 to i < len, and
        • If numString[i] is ‘6’, make it ‘9’.
        • Else, if it is ‘9’, make it ‘6’.
      • Now, if the numeric value of numString is less than or equal to maxVal, and not the same as num, and the first character of numString is not ‘0’, increase the value of count by 1.
  • Finally, return the value of count.
Time Complexity

O(N * log N), where N is the value of ‘MAXVAL’.

 

We are checking all the numbers in the range 1 to N, one by one, and checking each digit of the number. Since a number can have log N digits.

 

So the overall complexity becomes O(N * logN).

Space Complexity

O(1)

 

We are not using any extra space.

Code Solution
(100% EXP penalty)
Special Numbers
Full screen
Console