788. Rotated Digits

Time: O(n log n)

Space: O(1)

Intuition

A number is "good" if it's valid when rotated (all digits are 0,1,2,5,6,8,9) AND different from original (has at least one 2,5,6,9).

Algorithm

1For each n from 1 to N: check if all digits are in {0,1,2,5,6,8,9} and at least one digit is in {2,5,6,9}.

Common Pitfalls

•Digits 3,4,7 make a number invalid. Must also have 2,5,6, or 9 to ensure rotated != original.

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?