นับจำนวนเต็ม ≤ n ที่มีหลักซ้ำกันใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะนับจำนวนจำนวนเต็มบวกที่ ≤ n ซึ่งมี อย่างน้อย 1 หลักที่ซ้ำกัน (at least one repeated digit)

ตัวอย่าง

Input: n = 200
Output: 38

แนวคิดการแก้ปัญหา (Complementary Counting)

แทนที่จะนับ "มีหลักซ้ำ" โดยตรง ให้คำนวณ: Total - ไม่มีหลักซ้ำ (unique digits)

• Total = n
• นับจำนวนที่มีหลักไม่ซ้ำกันทั้งหมด (Unique digit numbers)
• ผลลัพธ์ = n - unique_count

อัลกอริทึม

1. แปลง n เป็นอาร์เรย์หลัก (digits array)
2. นับจำนวนที่มีหลักไม่ซ้ำและมีความยาว < ความยาวของ n
3. ใช้ Digit DP / Backtracking นับจำนวนที่ ≤ n และไม่มีหลักซ้ำ
4. ลบออกจาก n

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

int solve(int n) {
    vector a;
    for (int x = n; x; x /= 10) a.push_back(x % 10);
    reverse(a.begin(), a.end());
    
    int ret = n;
    
    // นับจำนวนที่ไม่มีหลักซ้ำ ความยาว < a.size()
    for (int w = 1, d = 1; w < a.size(); ++w) {
        d *= min(9, 10 - w + 1);
        ret -= d;
    }
    
    // Lambda function สำหรับนับความยาว = a.size()
    auto go = [&]() {
        int b = (1 << 10) - 1;  // bitmask หลักที่ใช้ได้ (0-9)
        for (int i = 0; i < a.size(); ++i) {
            for (int d = (i < 1); d < a[i]; ++d) {
                int x = 0;
                if ((1 << d) & b) ++x;
                for (int j = i + 1; j < a.size(); ++j) x *= 10 - j;
                ret -= x;
            }
            if ((1 << a[i]) & b)
                b ^= (1 << a[i]);
            else
                return;
        }
        --ret;
    };
    
    go();
    return ret;
}

int main() {
    cout << solve(200) << endl;
    return 0;
}

ผลลัพธ์

38

คำอธิบายโค้ด

• b = bitmask ติดตามหลักที่ใช้แล้ว (bit i = 1 หมายถึงหลัก i ยังใช้ได้)
• ลูปแรก: นับจำนวน unique-digit ที่มีความยาวสั้นกว่า n
• Lambda go(): นับจำนวน unique-digit ความยาวเท่า n และ ≤ n
• ใช้ combinatorics: สำหรับตำแหน่งที่เหลือ มี (10 - จำนวนหลักที่ใช้แล้ว) ตัวเลือก

สรุป

ใช้ Complementary Counting + Digit DP + Bitmask นับจำนวนที่มีหลักซ้ำได้อย่างมีประสิทธิภาพ หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ