จำนวนเลขที่มีตัวเลขซ้ำใน C++

คำอธิบายปัญหา

ให้จำนวนเต็มบวก N หาจำนวนจำนวนเต็มบวก ≤ N ที่มีตัวเลขซ้ำอย่างน้อย 1 ตัว

ตัวอย่าง

N = 99 → Output: 9 (คือ 11,22,33,44,55,66,77,88,99)

แนวทางแก้ปัญหา: Complementary Counting

นับจำนวนที่ ไม่มีตัวเลขซ้ำ แล้วลบออกจาก N

ขั้นตอน

1. แปลง N+1 เป็นอาร์เรย์หลัก (digit array) arr
2. นับจำนวนที่ไม่ซ้ำและมีหลักน้อยกว่า N: Σ 9 × A(9, i-1) สำหรับ i=1..n-1
   • A(m,n) = m × (m-1) × ... × (m-n+1) (Permutation)
3. นับจำนวนที่ไม่ซ้ำและมีหลักเท่ากัน N (Digit DP แบบ greedy):
   • เดินทีละหลักจากซ้ายไปขวา
   • สำหรับหลักที่ i ลองวางตัวเลข 0..digit-1 (หลักแรก 1..digit-1)
   • ข้ามตัวเลขที่ใช้แล้ว (visited set)
   • เพิ่ม A(9-i, n-i-1) สำหรับแต่ละตัวเลือกที่ถูกต้อง
   • ถ้าตัวเลขปัจจุบันซ้ำกับ visited → หยุด
4. ผลลัพธ์ = N - จำนวนที่ไม่ซ้ำ

ฟังก์ชัน A(m,n)

int A(int m, int n) {
    int ret = 1;
    for(int i=0; i<n; i++) ret *= m--;
    return ret;
}

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

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

class Solution {
    int A(int m, int n) {
        int ret = 1;
        for(int i=0; i<n; i++) ret *= m--;
        return ret;
    }
    
public:
    int numDupDigitsAtMostN(int N) {
        vector<int> arr;
        for(int i=N+1; i>0; i/=10) arr.insert(arr.begin(), i%10);
        
        int ret = 0, n = arr.size();
        // นับจำนวนที่ไม่ซ้ำและหลักน้อยกว่า n
        for(int i=1; i<n; i++) ret += 9 * A(9, i-1);
        
        // นับจำนวนที่ไม่ซ้ำและหลักเท่ากัน n
        unordered_set<int> visited;
        for(int i=0; i<n; i++) {
            int digit = arr[i];
            for(int j = (i==0?1:0); j<digit; j++) {
                if(visited.count(j)) continue;
                ret += A(9-i, n-i-1);
            }
            if(visited.count(digit)) break;
            visited.insert(digit);
        }
        return N - ret;
    }
};

ความซับซ้อน

• เวลา: O(log N) ~ O(จำนวนหลัก)
• พื้นที่: O(1)