788. Rotated Digits

MediumView on LeetCode

Math

Time: O(n log n)

Space: O(1)

Problem Overview

A rotated digit is valid only for 0, 1, 2, 5, 6, 8, 9 (3, 4, 7 break when flipped upside-down).

Intuition

A rotated digit is valid only for 0, 1, 2, 5, 6, 8, 9 (3, 4, 7 break when flipped upside-down). A "good" number must use only valid digits and contain at least one of 2, 5, 6, or 9 so that rotating 180° produces a different number — all 0/1/8 digits would look the same.

Algorithm

1Loop n from 1 to N inclusive.
2For each n, scan digits: reject if any digit is 3, 4, or 7.
3Track whether any digit is 2, 5, 6, or 9 (forces rotation to differ).
4If both checks pass, increment the count.
5Return total count.

Example Walkthrough

Input: N = 10

1.1, 2, 5, 6, 9 are good among 1..10 (2→5, 5→2, 6→9, 9→6 when rotated).
2.0 is invalid as a positive integer in the range; 3, 4, 7 have bad digits.

Output: 4

Common Pitfalls

•Digits 3, 4, 7 invalidate the entire number.
•A number made only of 0, 1, 8 rotates to itself — exclude unless a 2/5/6/9 appears.
•Leading zeros do not appear in the integer range 1..N.

788.cs

// Approach: Brute-force 1 to n; a number is valid if every digit is rotatable (not 3/4/7) and at least one digit actually changes (2,5,6,9).
// Time: O(n log n) Space: O(1)

public class Solution
{
    public int RotatedDigits(int n)
    {
        int ans = 0;

        for (int i = 1; i <= n; ++i)
        {
            if (IsGoodNumber(i))
                ++ans;
        }

        return ans;
    }

    private bool IsGoodNumber(int i)
    {
        bool isRotated = false;

        foreach (char c in i.ToString())
        {
            if (c == '0' || c == '1' || c == '8')
                continue;
            if (c == '2' || c == '5' || c == '6' || c == '9')
                isRotated = true;
            else
                return false;
        }

        return isRotated;
    }
}

Was this solution helpful?