Jobs

Interviews

Discussions

Rotated Digits

Medium

Arista Networks

3 views

Topics:

ArraysDynamic Programming

An integer x is a good if after rotating each digit individually by 180 degrees, we get a valid number that is different from x. Each digit must be rotated - we cannot choose to leave it alone.

A number is valid if each digit remains a digit after rotation. For example:

0, 1, and 8 rotate to themselves,
2 and 5 rotate to each other (in this case they are rotated in a different direction, in other words, 2 or 5 gets mirrored),
6 and 9 rotate to each other, and
the rest of the numbers do not rotate to any other number and become invalid.

Given an integer n, return the number of good integers in the range [1, n].

Example 1:

Input: n = 10
Output: 4
Explanation: There are four good numbers in the range [1, 10] : 2, 5, 6, 9.
Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.

Example 2:

Input: n = 1
Output: 0

Example 3:

Input: n = 2
Output: 1

Constraints:

1 <= n <= 10⁴

Rotated Digits

Medium

Arista Networks

3 views

Topics:

ArraysDynamic Programming

A number is valid if each digit remains a digit after rotation. For example:

0, 1, and 8 rotate to themselves,
2 and 5 rotate to each other (in this case they are rotated in a different direction, in other words, 2 or 5 gets mirrored),
6 and 9 rotate to each other, and
the rest of the numbers do not rotate to any other number and become invalid.

Given an integer n, return the number of good integers in the range [1, n].

Example 1:

Input: n = 10
Output: 4
Explanation: There are four good numbers in the range [1, 10] : 2, 5, 6, 9.
Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.

Example 2:

Input: n = 1
Output: 0

Example 3:

Input: n = 2
Output: 1

Constraints:

1 <= n <= 10⁴

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for 'N'? Can 'N' be zero or negative?
Are there any invalid digits in the input that I should consider, beyond the digits 2, 5, 6, and 9?
By 'rotated', do you strictly mean a 180-degree rotation, maintaining the same number of digits?
Is there a specific return value I should use if no good numbers exist in the range [1, N]?
Should I consider any potential integer overflow issues when N is very large?

Brute Force Solution

Approach

The brute force approach to this problem involves checking every number within the given range. For each number, we'll determine if it's a good number, meaning it becomes a different valid number when rotated 180 degrees.

Here's how the algorithm would work step-by-step:

Start with the first number in the range.
Check if this number contains any digits that are not allowed (3, 4, or 7). If it does, it cannot be a good number, so move to the next number.
If the number only contains allowed digits (0, 1, 2, 5, 6, 8, 9), rotate the number by mentally replacing digits (0 stays 0, 1 stays 1, 2 becomes 5, 5 becomes 2, 6 becomes 9, 8 stays 8, 9 becomes 6).
Compare the original number with the rotated number. If they are different, the original number is a good number.
If the original and rotated numbers are the same, the number is not a good number.
Keep track of how many good numbers you find.
Repeat steps 2-5 for every number within the specified range.
The total count of good numbers is the answer.

Code Implementation

def rotated_digits(number_limit):
    good_numbers_count = 0

    for current_number in range(1, number_limit + 1):
        number_string = str(current_number)
        is_good_number = True
        rotated_number_string = ""

        for digit_char in number_string:
            if digit_char in ('3', '4', '7'):
                is_good_number = False
                break

            # Build rotated number string based on digits
            if digit_char == '0':
                rotated_number_string += '0'
            elif digit_char == '1':
                rotated_number_string += '1'
            elif digit_char == '2':
                rotated_number_string += '5'
            elif digit_char == '5':
                rotated_number_string += '2'
            elif digit_char == '6':
                rotated_number_string += '9'
            elif digit_char == '8':
                rotated_number_string += '8'
            elif digit_char == '9':
                rotated_number_string += '6'

        if is_good_number:
            # Check to see rotated version is different
            if number_string != rotated_number_string:
                good_numbers_count += 1

    return good_numbers_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each number from 1 to n. For each number, it checks if it contains invalid digits (3, 4, 7) and then, if valid, it rotates the digits. The digit checking and rotation take constant time. Therefore, the dominant operation is the single loop iterating up to n, making the overall time complexity O(n).

Space Complexity

O(1) – The brute force approach described checks each number within the range [1, N] to determine if it's a 'good' number. The algorithm doesn't explicitly create any data structures that scale with N such as arrays, lists, or hashmaps. It only stores a constant number of variables like the current number being checked and a counter for the good numbers. Therefore, the auxiliary space used is constant, regardless of the size of N.

Optimal Solution

Approach

We need to count numbers that become a different valid number when rotated 180 degrees. The clever approach is to build valid rotated numbers digit by digit, avoiding unnecessary checks. This saves time compared to checking every single number individually.

Here's how the algorithm would work step-by-step:

Recognize that only certain digits (0, 1, 2, 5, 6, 8, and 9) can be part of a rotated number. Other digits invalidate the number immediately.
Consider each digit position in the number, starting from the most significant digit.
For each position, explore the possible valid digits (0, 1, 2, 5, 6, 8, 9) that are less than the original number's digit at that position.
Check if a valid rotated number is possible from that point forward. A number is valid if at least one of its digits rotates to a different digit (2, 5, 6, or 9).
Add the count of possible valid rotated numbers to the total count.
If the current digit is a valid rotated digit (0, 1, 2, 5, 6, 8, or 9), move on to the next digit position and repeat the process.
Handle the special case where the number itself is a valid rotated number. If it is, add 1 to the total count.
The final count is the total number of valid rotated numbers up to the given number.

Code Implementation

def rotated_digits(number):
    count_valid_rotated = 0
    string_number = str(number)
    number_length = len(string_number)

    def is_good_number(index, is_different, is_smaller):
        if index == number_length:
            return is_different

        upper_bound = int(string_number[index]) if is_smaller else 9
        total_numbers = 0

        for digit in range(upper_bound + 1):
            if digit in [3, 4, 7]:
                continue

            new_is_different = is_different or digit in [2, 5, 6, 9]
            new_is_smaller = is_smaller or digit < int(string_number[index])

            total_numbers += is_good_number(index + 1, new_is_different, new_is_smaller)

        return total_numbers

    count_valid_rotated = is_good_number(0, False, True)

    return count_valid_rotated

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The algorithm iterates through the digits of the input number n. The number of digits in n is proportional to log base 10 of n. For each digit, a constant amount of work is performed: checking valid digits and recursively calculating possibilities. Since the number of digits is logarithmic with respect to n, the time complexity is O(log n).

Space Complexity

O(log N) – The algorithm's space complexity is primarily determined by the depth of the recursion, which corresponds to the number of digits in the input number N. Since the number of digits in N is proportional to log N (base 10), the maximum depth of the call stack will be log N. Therefore, the space required to store the call stack is O(log N). No other significant auxiliary data structures are created.

Edge Cases

Case	How to Handle
Input N is zero	Return 0, as no numbers less than or equal to 0 can be considered 'good'.
Input N is a single digit number (e.g., 2, 5, 6, 9)	Manually check if the number is a good number and return 1 or 0.
N is a power of 10 (e.g., 10, 100, 1000)	Ensure the loop iterates correctly and calculates the 'good' numbers accurately up to the power of 10.
N is very large (approaching integer limits)	The solution should be efficient enough to handle large values of N without exceeding time limits or causing integer overflow (consider using int vs long).
Numbers containing only 'good' digits (2, 5, 6, 9)	Numbers like 259 should be correctly identified as 'good'.
Numbers containing no 'good' digits but containing valid digits (0, 1, 8)	Numbers like 108 should be correctly identified as not 'good'.
Numbers containing both 'good' and invalid digits (3, 4, 7)	Numbers like 32 should be correctly identified as not 'good'.
N contains leading zeros (invalid input but might occur)	The problem statement implies that N is a positive integer, so you should assume there will be no leading zeros or the input will be handled to remove them.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for 'N'? Can 'N' be zero or negative?
Are there any invalid digits in the input that I should consider, beyond the digits 2, 5, 6, and 9?
By 'rotated', do you strictly mean a 180-degree rotation, maintaining the same number of digits?
Is there a specific return value I should use if no good numbers exist in the range [1, N]?
Should I consider any potential integer overflow issues when N is very large?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the first number in the range.
Check if this number contains any digits that are not allowed (3, 4, or 7). If it does, it cannot be a good number, so move to the next number.
If the number only contains allowed digits (0, 1, 2, 5, 6, 8, 9), rotate the number by mentally replacing digits (0 stays 0, 1 stays 1, 2 becomes 5, 5 becomes 2, 6 becomes 9, 8 stays 8, 9 becomes 6).
Compare the original number with the rotated number. If they are different, the original number is a good number.
If the original and rotated numbers are the same, the number is not a good number.
Keep track of how many good numbers you find.
Repeat steps 2-5 for every number within the specified range.
The total count of good numbers is the answer.

Code Implementation

def rotated_digits(number_limit):
    good_numbers_count = 0

    for current_number in range(1, number_limit + 1):
        number_string = str(current_number)
        is_good_number = True
        rotated_number_string = ""

        for digit_char in number_string:
            if digit_char in ('3', '4', '7'):
                is_good_number = False
                break

            # Build rotated number string based on digits
            if digit_char == '0':
                rotated_number_string += '0'
            elif digit_char == '1':
                rotated_number_string += '1'
            elif digit_char == '2':
                rotated_number_string += '5'
            elif digit_char == '5':
                rotated_number_string += '2'
            elif digit_char == '6':
                rotated_number_string += '9'
            elif digit_char == '8':
                rotated_number_string += '8'
            elif digit_char == '9':
                rotated_number_string += '6'

        if is_good_number:
            # Check to see rotated version is different
            if number_string != rotated_number_string:
                good_numbers_count += 1

    return good_numbers_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Recognize that only certain digits (0, 1, 2, 5, 6, 8, and 9) can be part of a rotated number. Other digits invalidate the number immediately.
Consider each digit position in the number, starting from the most significant digit.
For each position, explore the possible valid digits (0, 1, 2, 5, 6, 8, 9) that are less than the original number's digit at that position.
Check if a valid rotated number is possible from that point forward. A number is valid if at least one of its digits rotates to a different digit (2, 5, 6, or 9).
Add the count of possible valid rotated numbers to the total count.
If the current digit is a valid rotated digit (0, 1, 2, 5, 6, 8, or 9), move on to the next digit position and repeat the process.
Handle the special case where the number itself is a valid rotated number. If it is, add 1 to the total count.
The final count is the total number of valid rotated numbers up to the given number.

Code Implementation

def rotated_digits(number):
    count_valid_rotated = 0
    string_number = str(number)
    number_length = len(string_number)

    def is_good_number(index, is_different, is_smaller):
        if index == number_length:
            return is_different

        upper_bound = int(string_number[index]) if is_smaller else 9
        total_numbers = 0

        for digit in range(upper_bound + 1):
            if digit in [3, 4, 7]:
                continue

            new_is_different = is_different or digit in [2, 5, 6, 9]
            new_is_smaller = is_smaller or digit < int(string_number[index])

            total_numbers += is_good_number(index + 1, new_is_different, new_is_smaller)

        return total_numbers

    count_valid_rotated = is_good_number(0, False, True)

    return count_valid_rotated

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input N is zero	Return 0, as no numbers less than or equal to 0 can be considered 'good'.
Input N is a single digit number (e.g., 2, 5, 6, 9)	Manually check if the number is a good number and return 1 or 0.
N is a power of 10 (e.g., 10, 100, 1000)	Ensure the loop iterates correctly and calculates the 'good' numbers accurately up to the power of 10.
N is very large (approaching integer limits)	The solution should be efficient enough to handle large values of N without exceeding time limits or causing integer overflow (consider using int vs long).
Numbers containing only 'good' digits (2, 5, 6, 9)	Numbers like 259 should be correctly identified as 'good'.
Numbers containing no 'good' digits but containing valid digits (0, 1, 8)	Numbers like 108 should be correctly identified as not 'good'.
Numbers containing both 'good' and invalid digits (3, 4, 7)	Numbers like 32 should be correctly identified as not 'good'.
N contains leading zeros (invalid input but might occur)	The problem statement implies that N is a positive integer, so you should assume there will be no leading zeros or the input will be handled to remove them.