788. Rotated Digits

題目 / Problem

中文： 給定一個整數 n。對於每個數字 x (1 ≤ x ≤ n)，把它的每一位數字都旋轉 180 度（必須全部旋轉，不能保留原狀）。如果旋轉後仍然是一個合法整數，並且與原本的 x 不同，那麼 x 就是一個「好數」。求 [1, n] 範圍內好數的個數。

每個數字的旋轉規則： - 0、1、8 旋轉後還是它自己 - 2 和 5 互相旋轉 - 6 和 9 互相旋轉 - 3、4、7 旋轉後不是合法數字

English: Given an integer n, count integers x in [1, n] such that when each digit is rotated 180°, the result is a valid number different from x. Every digit must be rotated (you may not skip a digit). Digit rotation rules: 0/1/8 map to themselves; 2↔5; 6↔9; 3/4/7 are invalid.

Constraints: 1 <= n <= 10^4.

Example: n = 10 → output 4. The good numbers are 2, 5, 6, 9. Numbers like 1, 8, 10 rotate to themselves so they are not good; 3, 4, 7 contain invalid digits.

名詞解釋 / Glossary

• Good number / 好數：所有位數旋轉後仍合法，且整體與原數不同。A number whose digits are all rotatable and which changes after rotating every digit.
• Brute force / 暴力枚舉：直接檢查 [1, n] 中每一個數字。Iterate through all candidates and test each one — simple but works only when n is small.
• Digit extraction / 取位數：用 % 10 取個位數，用 / 10 砍掉個位，逐步處理一個整數的每一位。Use % 10 to grab the last digit and /= 10 to drop it; repeat to walk through all digits.
• Boolean flags / 布林旗標：兩個 bool 變數紀錄「是否出現非法數字」和「是否出現會改變的數字」。Two flags track (a) whether any invalid digit appeared and (b) whether at least one digit actually changes under rotation.
• std::string / C++ 字串：C++ 標準庫的字串型別，可以用 to_string(x) 把整數轉成字串、用範圍 for 逐字元處理。STL string class; to_string(x) converts an int to a string and a range-based for loops over its characters.

思路

最直接的想法是把 [1, n] 中的每個數字都拿來檢查。對每個數字 x，我們要逐位檢查它的數字：只要出現 3、4 或 7，整個數字立刻作廢，因為旋轉後不是合法數字；如果所有位都是 {0,1,2,5,6,8,9} 之一，再看有沒有任何一位是 {2,5,6,9}——這四個數字旋轉後會變成不同的數字。如果有，整個 x 旋轉後就和原本不同，是「好數」。如果整個數字只由 {0,1,8} 組成，那麼旋轉後完全不變，不算好數。題目限制 n ≤ 10^4，最多檢查一萬個數，每個數字最多 5 位，用最簡單的迴圈就足夠快，不需要動態規劃或數位 DP 之類的進階技巧。雖然有「數位 DP」的更通用解法（適用於 n 很大的情形），但對這題來說反而把問題複雜化。

The simplest approach is to test every integer from 1 to n directly. For each x, walk through its digits using % 10 and / 10. If any digit is 3, 4, or 7, the rotation is invalid — discard x. Otherwise, check whether at least one digit lies in {2, 5, 6, 9} — those are the digits that actually change when rotated. A number made up only of {0, 1, 8} rotates to itself and therefore is not good. So the rule reduces to two boolean flags per number: "has an invalid digit?" and "has a changing digit?". Because n ≤ 10^4, brute force is plenty fast (at most ~50,000 digit checks total). A digit-DP solution would be overkill and harder to read for the audience this article targets.

逐步走查 / Walkthrough

以 n = 10 為例，逐個檢查 x = 1..10 / Trace n = 10, checking x from 1 to 10:

最終計數 / Final count = 4（即 2, 5, 6, 9）。

Solution — C

// 演算法：對 [1, n] 中每個整數，用 % 10 與 / 10 逐位檢查。
// Algorithm: for each x in [1..n], extract digits via % 10 and / 10.
// 出現 3/4/7 立即作廢；只要有一位屬於 {2,5,6,9} 就算「好數」。
// Reject if any digit is 3/4/7; mark good if any digit is in {2,5,6,9}.

int rotatedDigits(int n) {
    int count = 0;                          // 好數的數量 / running count of good numbers
    for (int x = 1; x <= n; x++) {          // 枚舉每個候選 / iterate every candidate in [1, n]
        int y = x;                          // 複製 x，避免破壞迴圈變數 / copy so we can chip digits off without touching x
        int valid = 1;                      // 1 表示目前每位都合法 / 1 = no invalid digit (3/4/7) seen yet
        int changed = 0;                    // 0 表示目前所有位都旋轉到自己 / 0 = no digit in {2,5,6,9} seen yet
        while (y > 0) {                     // 從個位開始一路砍到 0 / peel digits until y becomes 0
            int d = y % 10;                 // d 是目前的個位數 / d is the current ones digit
            y /= 10;                        // 砍掉個位，準備處理下一位 / drop the ones digit; '/' is integer division
            if (d == 3 || d == 4 || d == 7) {  // 這三個旋轉後不是合法數字 / these rotate to nothing valid
                valid = 0;                  // 整個 x 直接作廢 / mark x as invalid
                break;                      // 不必再看其他位 / no need to inspect remaining digits
            }
            if (d == 2 || d == 5 || d == 6 || d == 9) {  // 這四個旋轉後會變成另一個數字 / these flip to a different digit
                changed = 1;                // 至少有一位會改變 / at least one digit actually changes
            }
            // d == 0/1/8 時不做事，因為旋轉後不變 / for 0/1/8 nothing to flag — they map to themselves
        }
        if (valid && changed) count++;      // 兩個條件都成立才是好數 / good = all digits valid AND something changes
    }
    return count;                           // 回傳答案 / return final count
}

Solution — C++

// 演算法和 C 版相同；改用 std::string 把數字轉成字串，逐字元檢查。
// Same algorithm; we convert x to a std::string and scan characters.
// 這樣示範一些 C++ 慣用法：to_string、range-for、bool 旗標。
// Demonstrates idiomatic C++ features: to_string, range-based for, bool flags.

#include <string>     // 引入 std::string / for std::string and std::to_string
using namespace std;

class Solution {
public:
    int rotatedDigits(int n) {
        int count = 0;                              // 好數計數 / counter for good numbers
        for (int x = 1; x <= n; ++x) {              // 枚舉 [1, n] / loop through every candidate
            string s = to_string(x);                // 把整數轉成字串，例如 25 -> "25" / int -> string conversion
            bool valid = true;                      // 是否每位都能合法旋轉 / true while no invalid digit found
            bool changed = false;                   // 是否至少一位會改變 / true once we see a {2,5,6,9}
            for (char c : s) {                      // range-for：逐字元遍歷字串 / iterate over each character of s
                if (c == '3' || c == '4' || c == '7') {  // 比較字元用單引號 / chars are compared with single quotes
                    valid = false;                  // 出現非法字元 / invalid digit detected
                    break;                          // 立刻跳出迴圈 / no need to scan further
                }
                if (c == '2' || c == '5' || c == '6' || c == '9') {  // 旋轉後會變的位 / digits that change under rotation
                    changed = true;                 // 標記至少有一位會變 / mark that x will differ after rotation
                }
                // '0', '1', '8' 旋轉後不變，不需要旗標 / '0','1','8' rotate to themselves — no flag needed
            }
            if (valid && changed) ++count;          // 同時成立才計入 / both conditions must hold
        }
        return count;                               // 回傳答案 / return result
    }
};

複雜度 / Complexity

• Time: O(n · log₁₀ n) — 我們檢查 n 個整數，每個整數最多有 log₁₀ n + 1 位（這題最多 5 位），所以總工作量正比於數字總位數。We scan every integer up to n, and each one has at most ⌊log₁₀ n⌋ + 1 ≈ 5 digits, so the total work is bounded by n times the digit count.
• Space: O(1)（C 版）/ O(log n)（C++ 版，因 to_string 暫存了字串）— 除了少數計數變數外不需要額外資料結構。Aside from the loop counters and (in C++) the temporary string, we use no extra data structures.

Pitfalls & Edge Cases

• 以為「全部 0/1/8」也算好數 / Thinking numbers made only of {0,1,8} are good：例如 1, 10, 18, 81, 88 旋轉後等於自己，所以不是好數。題目要求結果必須不同於原本的 x。These rotate to themselves; the problem requires the rotated number to be different.
• 忘了檢查非法數字 / Forgetting the invalid-digit check：只要出現 3, 4, 7 中任何一個就要整個丟掉，不能只計算「沒包含 0/1/8」的數字。Any single occurrence of 3/4/7 invalidates the whole number, so a {0,1,8}-free check alone is not enough.
• 修改迴圈變數 / Mutating the loop counter：在 C 版中我們用 int y = x; 拷貝一份再做 y /= 10，否則會破壞外層 for 迴圈。Always copy x before chipping digits with /= 10; otherwise the outer loop counter gets clobbered.
• 整數除法的方向 / Integer division direction：y /= 10 是整數除法，會直接捨去小數點後的部分。例如 25 / 10 == 2。In C/C++, / between two ints truncates toward zero — this is the property we rely on to "drop" a digit.
• 字元 vs 整數比較（C++）/ Comparing chars vs ints (C++)：if (c == 3) 是錯的；字元 '3' 的 ASCII 值是 51，必須寫 c == '3'。Use '3' (the character literal) when comparing with a char, not the integer 3.