Last Updated: 23 Mar, 2021
##### Strange Numbers
Hard
Problem statement

#### Note :

``````The rotated number can be greater(or smaller) than the original number.
``````

#### Input Format :

``````The first line of the input contains an integer βTβ representing the number of test cases.

The first line of each test case contains a single integer βNβ denoting the integer given by Alice.
``````

#### Output Format :

``````For each test case, print the number of strange numbers between 1 and βNβ inclusive.

The output of 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 <= 5
1 <= N <= 10 ^ 5

Time Limit: 1sec
``````
Approaches

## 01Approach

The idea here is to perform a breadth-first search over all the numbers from 1 to βNβ inclusive with 0, 1, 6, 8, and 9 as their digits. Initially, we will insert all the numbers between 1 to βNβ  inclusive having a single - digit with 0 or 1 or 6 or 8 or 9 as their digit into a queue. We will gradually increase the length(i.e., number of digits) of the numbers present in the queue and insert it into the queue if the number lies between 1 to βNβ inclusive. Refer to the below diagram for a clear understanding.

For all the numbers present in the queue, we will check if the current number is a strange number.

Algorithm:

• Declare an integer, say βcntStrangeβ to count the total number of strange numbers in a given range, and initialize it with 0.
• Declare an integer, say βcurrNumberβ, to keep track of the current number during our BFS traversal.
• Declare a queue of integers.
• Run a loop for βdigitβ in [0, 1, 6, 8, 9]:
• If βdigitβ lies between 1 and βNβ inclusive
• Insert βdigitβ into the queue
• Run a loop until the queue is not empty:
• Store the front of the queue in βcurrNumberβ and remove it from the queue.
• Call the βisStrangeNumberβ function to check if βcurrNumberβ is a strange number or not.
• If βcurrNumberβ is a strange number:
• Increment βcntStrangeβ i.e., do cntStrange = cntStrange + 1.
• Append digits 0, 1, 6, 8, and 9 to βcurrNumberβ
• Run a loop for βdigitβ in [0, 1, 6, 8, 9]:
• Declare an integer, say βappendedNumberβ
• Update βappendedNumberβ as βappendedNumberβ = currNumber * 10 + digit
• If βappendedNumberβ lies between 1 and βNβ, inclusive
• Insert βappendedNumberβ into the queue.
• Return βcntStrangeβ.

Description of βisStrangeNumberβ function

This function is used to check whether the current number is a strange number or not.

This function will take one parameter:

• currNumber: An integer denoting the current number.

bool isStrangeNumber(currNumber):

• Declare a variable βrotatedNumberβ to store the value of βcurrNumberβ after rotating 180 degrees.
• Declare a variable βdummyβ and initialize it with βcurrNumberβ.
• Run a loop while βdummyβ is greater than 0.
• Declare a variable βcurrDigitβ and initialize it with the rightmost digit of βdummyβ, i.e., do currDigit = dummy % 10.
• Remove the rightmost digit of βdummyβ, i.e., do dummy = dummy / 10
• If βcurrDigitβ is 6, then make it 9, or if the βcurrDigit is 9, make it 6, i.e., rotate the βcurrDigitβ by 180 degrees.
• Append the βcurrDigitβ to βrotatedNumberβ i.e. do rotatedNumber = rotatedNumber * 10 + currDigit.
• If βcurrNumberβ is not equal to βrotatedNumberβ then return true,  as the current number follows properties of a strange number.
• Else return false, as the current number does not follow properties of a strange number as after rotating, the number must be different.