New update is available. Click here to update.

Last Updated: 23 Mar, 2021

Hard

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

```
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.
```

```
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.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 5
1 <= N <= 10 ^ 5
Time Limit: 1sec
```

Approaches

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

- If βdigitβ lies between 1 and βNβ inclusive
- 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.

The idea here is to perform a depth-first search over all the numbers from 1 to βNβ inclusive with 0, 1, 6, 8, and 9 as their digits. Initially, we will start the depth-first search from all the numbers between 1 to βNβ inclusive having a single - digit with 0 or 1 or 6 or 8 or 9 as their first digit. We will gradually increase the length(i.e., number of digits) of the numbers and recursively do a depth-first search if the number lies between 1 to βNβ inclusive. For every number that we encounter during the depth-first search, we will check if it is a strange number or not. If it is a strange number, then we will increment our answer.

Algorithm:

- Declare an integer, say βcntStrangeβ to count the total number of strange numbers in a given range.
- Call the βdepthFirstSearchβ function with βNβ and 0 as arguments and store its returned value into βcntStrangeβ
- 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.

Description of βdepthFirstSearchβ function

This function will take two parameters:

- N: An integer given in the problem.
- currNumber: An integer denoting the current number in depth-first search.

int depthFirstSearch(N, currNumber):

- Declare a variable βanswerβ to count the total number of strange numbers in a given range and initialize it with 0.
- Call the βisStrangeNumberβ function to check if βcurrNumberβ is a strange number or not.
- If βcurrNumberβ is a strange number:
- Increment βanswerβ i.e., do answer = answer + 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β
- Make appendedNumber = currNumber * 10 + digit
- If βappendedNumberβ lies between 1 and βNβ, inclusive
- Declare an integer, say βcurrAnswerβ
- Call the βdepthFirstSearchβ function with βNβ and βappendedNumberβ as arguments and store its returned value into βcurrAnswerβ
- Add βcurrAnswerβ to the βanswerβ i.e. do answer = answer + currAnswer

- Return βanswerβ