Strange Numbers

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.

O(log(N) *  5 ^ K), where ‘N’ is the number given in the problem and ‘K’ is the number of digits in ‘N’.

In the worst case, we can have at most ‘K’ digits in any strange number, and for every digit, we have 5 choices, i.e., 0, 1, 6, 8, and 9. Therefore, the number of possible different strange numbers can be (5 ^ K), i.e.,

(5 choices for 1st digit) * (5 choices for 2nd digit)  * . . . * (5 choices for Kth digit) 

And for each such possible number, the ‘isStrangeNumber’ function is called, which takes O(log(N)) time.

So, the total time complexity will be O(log(N) * 5 ^ K)

O(5 ^ K), where ‘K’ is the number of digits in the given integer ‘N’.

In the worst case, we have to store all (5 ^ K) enumerated numbers in the queue. This case happens during the last level traversal of our BFS algorithm. 

So, the total space complexity will be O(5 ^ K)