Special Numbers
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.

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

Question

Special Numbers

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.

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

Accepted Answer

Tip 1:
Tip 2:
Tip 3:

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1)

We are not using any extra space.

Time Complexity: O(nlogn)Explanation:

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

Java (SE 1.8)

/*
    Time Complexity: O((logN) * (5 ^ log(N)))
    Space Complexity: O(1),

    where N is the limit upto which special numbers are to be counted.
*/

import java.lang.StringBuilder;

public class Solution 
{
    public static int findSpecialNumbers(int maxVal) 
    {
        // Store the count of all special numbers in the given range.
        int count = 0;

        // Traverse through all numbers in the range and check whether it is
        // a special number or not.
        for (int num = 1; num <= maxVal; num++) 
        {
            StringBuilder numString = new StringBuilder();

            // Find the string representation of the number.
            numString.append(Integer.toString(num));

            boolean specialNum = true;

            // If any digit is not special, the number can't be a special number.
            for (int i = 0; i < numString.length(); i++) 
            {
                char a = numString.charAt(i);
                if (a == '2' || a == '3' || a == '4' || a == '5' || a == '7') 
                {
                    specialNum = false;
                }
            }


            if (specialNum == true) 
            {
                int len = numString.length();

                // Now, for rotating the number, we first reverse the string representation.
                numString.reverse();

                // Now, we replace every '6' by '9' and vice-versa.
                for (int i = 0; i < len; i++) 
                {
                    if (numString.charAt(i) == '6') 
                    {
                        numString.setCharAt(i, '9');
                    } 
                    else if (numString.charAt(i) == '9') 
                    {
                        numString.setCharAt(i, '6');
                    }
                }

                String numStr = numString.toString();

                // If it is a special number, increase the value of 'count' by 1.
                if (Integer.valueOf(numStr) <= maxVal && numStr.charAt(0) != '0' && Integer.valueOf(numStr) != num) 
                {
                    count++;
                }
            }
        }

        return count;
    }
}

C++ (g++ 5.4)

/*
    Time Complexity: O(N * log(N))
    Space Complexity: O(1),

    where N is the limit upto which special numbers are to be counted.
*/

int findSpecialNumbers(int maxVal) 
{
    // Store the count of all special numbers in the given range.
    int count = 0;

    // Traverse through all numbers in the range and check whether it is
    // a special number or not.
    for (int num = 1; num <= maxVal; num++) 
    {

        // Find the string representation of the number.
        string numString = to_string(num);

        bool specialNum = true;

        // If any digit is not special, the number can't be a special number.
        for (char a : numString) 
        {
            if (a == '2' or a == '3' or a == '4' or a == '5' or a == '7') 
            {
                specialNum = false;
            }
        }


        if (specialNum == true) 
        {

            int len = numString.size();

            // Now, for rotating the number, we first reverse the string representation.
            for (int i = 0; i < len / 2; i++) 
            {
                swap(numString[i], numString[len - 1 - i]);
            }
            
            // Now, we replace every '6' by '9' and vice-versa.
            for (int i = 0; i < len; i++) 
            {
                if (numString[i] == '6') 
                {
                    numString[i] = '9';
                }
                else if (numString[i] == '9') 
                {
                    numString[i] = '6';
                }
            }

            // If it is a special number, increase the value of 'count' by 1.
            if (stoi(numString) <= maxVal and numString[0] != '0' and stoi(numString) != num) 
            {
                count++;
            }
        }
    }
    
    return count;
}

Python (3.5)

'''
    Time Complexity: O(N * log(N))
    Space Complexity: O(1),

    where N is the limit upto which special numbers are to be counted.
'''

def findSpecialNumbers(maxVal):

    # Store the count of all special numbers in the given range.
    count = 0

    # Traverse through all numbers in the range and check whether it is a special number or not.
    for num in range(1,maxVal+1):

        # For python we will use list for representation of the number, as string are immutable.
        numString = [x for x in str(num)]

        specialNum = True

        # If any digit is not special, the number can't be a special number.
        for a in numString :
            if (a == '2' or a == '3' or a == '4' or a == '5' or a == '7'):
                specialNum = False

        if (specialNum == True):

            len1 = len(numString)

            # Now, for rotating the number, we first reverse the string representation.
            for i in range(len1//2):
                numString[i], numString[len1 - 1 - i] = numString[len1 - 1 - i], numString[i]
            
            # Now, we replace every '6' by '9' and vice-versa.
            for i in range(len1):
                if (numString[i] == '6') :
                    numString[i] = '9'
        
                elif (numString[i] == '9') :
                    numString[i] = '6'

            # If it is a special number, increase the value of 'count' by 1.
            # We need to convert numString to a string
            numString = "".join(numString)
            if (int(numString) <= maxVal and numString[0] != '0' and int(numString) != num):
                count += 1
    return count

Accepted Answer

Checking numbers having only special digits

The approach is to observe the fact that any special number will only have special digits in it. So, instead of checking all the numbers in the range, 1 to ‘MAXVAL’ independently, we can only check numbers that are made up of special digits only. For any special number, we can get more special numbers by appending one of the digits from 0,1,6,8,9 one by one at the end of the special number and check for the new number. The process of checking whether a number is special or not has been discussed in the other approach.

Steps:

Initialize a variable, say count=0. This will store the total count of special numbers in the given range.
Call the function, checkNumbers(0,maxVal,count).
Return the value of the count.

void checkNumbers(num , maxVal , count) {

If the value of num is more than maxVal, return.
Define a variable, say numString, to store the rotated string representation of num. Formally, make numString = rotate(num).
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.
Now, if num>0, call checkNumbers(num*10,maxVal,count). We call this function, only if num>0, because if we call it for num=0, it will form infinite loop.
Call checkNumbers(num*10+1,maxVal,count).
Call checkNumbers(num*10+6,maxVal,count).
Call checkNumbers(num*10+8,maxVal,count).
Call checkNumbers(num*10+9,maxVal,count).

String rotate(num) {

Define a variable, say numString to store the string representation of num.
Store the length of numString in len.
Run a loop from i=0 to iand swap characters at numString[i] and numString[len-1-i].
Run a loop from i=0 to i and
If numString[i] is ‘6’, make it ‘9’.
Else, if it is ‘9’, make it ‘6’.
Return, numString.

Space Complexity: O(1)Explanation:
O(1)

We are not using any extra space.
Time Complexity: OtherExplanation:
O((log N) * (5 ^ log N)), where N is the value of ‘MAXVAL’.

We are forming all special numbers one by one. Any number can in the given range have at most log(N) digits, and for each digit, there are 5 possible options. So, there can be 5^logN numbers. Each number will take O(log N) time to check whether it is a special number or not.

So, the overall complexity will become O(log N * 5 ^ log N)

Python (3.5)
''' Time Complexity: O((logN) * (5 ^ log(N))) Space Complexity: O(1), where N is the limit upto which special numbers are to be counted. ''' def rotate(num): # For python we will use list for representation of the number, as string are immutable. numString = [x for x in str(num)] len1 = len(numString) # Now, for rotating the number, we first reverse the string representation. for i in range(len1//2): numString[i], numString[len1 - 1 - i] = numString[len1 - 1 - i], numString[i] # Now, we replace every '6' by '9' and vice-versa. for i in range(len1): if (numString[i] == '6'): numString[i] = '9' elif (numString[i] == '9'): numString[i] = '6' return "".join(numString) def checkNumbers(num, maxVal, count): # If the number is more than 'maxVal', we simply return. if (num > maxVal): return count # Find the string representation of the number after rotation. numString = rotate(num) # If the number after rotation is within the range, and it is not equal to the original number, then it is a special number. if (int(numString) <= maxVal and numString [0] != '0' and int(numString) != num): count += 1 # Only call this function for a number greater than 0. if (num > 0): count = checkNumbers(num * 10, maxVal, count) # Append all special digits at the end of the string one by one and recursively call the function. count = checkNumbers(num * 10 + 1, maxVal, count) count = checkNumbers(num * 10 + 6, maxVal, count) count = checkNumbers(num * 10 + 8, maxVal, count) count = checkNumbers(num * 10 + 9, maxVal, count) return count def findSpecialNumbers(maxVal): # Store the count of special numbers in the given range. count = 0 # Call the function, which will call itself recursively for all possible special numbers in the range, and increase the value of count. count = checkNumbers(0, maxVal, count) return count

C++ (g++ 5.4)
/* Time Complexity: O((logN) * (5 ^ log(N))) Space Complexity: O(1), where N is the limit upto which special numbers are to be counted. */ string rotate(int num) { // Find the string representation of the number. string numString = to_string(num); int len = numString.size(); // Now, for rotating the number, we first reverse the string representation. for (int i = 0; i < len / 2; i++) { swap(numString[i], numString[len - 1 - i]); } // Now, we replace every '6' by '9' and vice-versa. for (int i = 0; i < len; i++) { if (numString[i] == '6') { numString[i] = '9'; } else if (numString[i] == '9') { numString[i] = '6'; } } return numString; } void checkNumbers(int num, int maxVal, int& count) { // If the number is more than 'maxVal', we simply return. if (num > maxVal) { return; } // Find the string representation of the number after rotation. string numString = rotate(num); // If the number after rotation is within the range, and it is not equal // to the original number, then it is a special number. if (stoi(numString) <= maxVal and numString [0] != '0' and stoi(numString) != num) { count++; } // Only call this function for a number greater than 0. if (num > 0) { checkNumbers(num * 10, maxVal, count); } // Append all special digits at the end of the string one by one, // and recursively call the function. checkNumbers(num * 10 + 1, maxVal, count); checkNumbers(num * 10 + 6, maxVal, count); checkNumbers(num * 10 + 8, maxVal, count); checkNumbers(num * 10 + 9, maxVal, count); } int findSpecialNumbers(int maxVal) { // Store the count of special numbers in the given range. int count = 0; // Call the function, which will call itself recursively for all possible // special numbers in the range, and increase the value of count. checkNumbers(0, maxVal, count); return count; }

Java (SE 1.8)
/* Time Complexity: O((logN) * (5 ^ log(N))) Space Complexity: O(1), where N is the limit upto which special numbers are to be counted. */ import java.lang.StringBuilder; public class Solution { public static int count; public static String rotate(int num) { StringBuilder numString = new StringBuilder(); // Find the string representation of the number. numString.append(Integer.toString(num)); int len = numString.length(); // Now, for rotating the number, we first reverse the string representation. numString.reverse(); // Now, we replace every '6' by '9' and vice-versa. for (int i = 0; i < len; i++) { if (numString.charAt(i) == '6') { numString.setCharAt(i, '9'); } else if (numString.charAt(i) == '9') { numString.setCharAt(i, '6'); } } return numString.toString(); } public static void checkNumbers(int num, int maxVal) { // If the number is more than 'maxVal', we simply return. if (num > maxVal) { return; } // Find the string representation of the number after rotation. String numString = rotate(num); // If the number after rotation is within the range, and it is not equal // to the original number, then it is a special number. if (Integer.valueOf(numString) <= maxVal && numString.charAt(0) != '0' && Integer.valueOf(numString) != num) { count++; } // Only call this function for a number greater than 0. if (num > 0) { checkNumbers(num * 10, maxVal); } // Append all special digits at the end of the string one by one, // and recursively call the function. checkNumbers(num * 10 + 1, maxVal); checkNumbers(num * 10 + 6, maxVal); checkNumbers(num * 10 + 8, maxVal); checkNumbers(num * 10 + 9, maxVal); } public static int findSpecialNumbers(int maxVal) { // Store the count of special numbers in the given range. count = 0; // Call the function, which will call itself recursively for all possible // special numbers in the range, and increase the value of count. checkNumbers(0, maxVal); return count; } }

Top Google Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Google Software Developer