โจทย์กำหนดลำดับที่ประกอบไปด้วยเลขสามหลัก $n$ ตัว ให้หาว่ามีกี่คู่ตัวเลขที่มีตัวเลขตรงกันอย่างน้อยหนึ่งหลัก

วิธีหนึ่งที่ง่ายที่สุดคือการตรวจสอบทั้งหมด ${n \choose 2}$ คู่ดูว่ามีอย่างน้อยหนึ่งหลักตรงกันหรือไม่ แต่จะไม่ได้คะแนนเต็มเพราะ Time Complexity $O(n^2)$ ช้าเกินไปสำหรับกรณีที่ $n$ มีค่ามากถึง $100\,000$

เราสามารถลดเวลาการทำงานได้สองวิธี

Solution 1: Counting

หากข้อมูลนำเข้าประกอบไปด้วยเลข $123$ 10 ตัว และ $159$ 5 ตัว สังเกตว่าจำนวนคู่ทั้งหมดจะนับได้จาก

• เลข $123$ จับคู่กันเอง ${10 \choose 2} = 45$ คู่
• เลข $159$ จับคู่กันเอง ${5 \choose 2} = 10$ คู่
• เลข $123$ จับคู่กับ $159$ ได้ $10 \times 5 = 50$ คู่

รวมเป็นทั้งหมด $105$ คู่

จากตัวอย่างนี้ ทำให้เราคิดวิธีแก้โจทย์กรณีทั่วไปได้ ขั้นตอนวิธีการแก้ปัญหาเป็นดังนี้

1. นับว่ามีเลข $000, 001, 002, \dots, 999$ ทั้งหมดกี่ตัว ในที่นี้จะนิยามให้ $cnt_i$ = จำนวนครั้งที่เลข $i$ ปรากฏ
2. นับจำนวนคู่ที่เกิดจากการจับคู่เลขเดียวกันเอง ได้ $\sum\limits_{i=000}^{999} {cnt_i \choose 2}$ คู่
3. นับจำนวนคู่ที่เกิดจากการจับคู่เลขที่มีอย่างน้อยหนึ่งหลักซ้ำกัน สำหรับเลข $i$ กับ $j$ จะจับคู่ได้ทั้งหมด $cnt_i \times cnt_j$ คู่
4. ตอบผลรวมจำนวนที่ได้จากขั้นที่ 2 และ 3

Solution 2: Inclusion—Exclusion

กำหนดให้

• $H$ คือเซตของคู่จำนวนที่มีเลขในหลักร้อยตรงกัน
• $T$ คือเซตของคู่จำนวนที่มีเลขในหลักสิบตรงกัน
• $U$ คือเซตของคู่จำนวนที่มีเลขในหลักหน่วยตรงกัน

เราต้องการหา $|H \cup T \cup U|$ ซึ่งสามารถหาได้จาก Inclusion—Exclusion principle:

$|H \cup T \cup U| = |H| + |T| + |U| - |H \cap T| - |H \cap U| - |T \cap U| + |H \cap T \cap U|$

ดังนั้น ระหว่างรับตัวเลขแต่ละตัวในข้อมูลนำเข้า เราจะนับว่ามีตัวเลขกี่ตัวที่มี

• หลักร้อย, หลักสิบ, หลักหน่วย เป็น $0, 1, 2, \dots, 9$ (เรียกว่า $h_i, t_i, u_i$ โดย $i=0,1,2,\dots,9$)
• หลักร้อยและสิบ, หลักร้อยและหน่วย, หลักสิบและหน่วย เป็น $00, 01, 02, \dots, 99$ (เรียกว่า $ht_i$, $hu_i$, $tu_i$ โดย $i = 00, 01, \dots, 99$)
• ทั้งสามหลักเป็น $000, 001, 002, \dots, 999$ (เรียกว่า $htu_i$ โดย $i = 000, 001, 002, \dots, 999$)

เราสามารถนับได้ว่ามีกี่คู่ตัวเลขที่มีหลักร้อยตรงกัน ($|H|$)ได้จาก $\sum\limits_{i=0}^{i=9} {h_i \choose 2}$ ส่วนหลักอื่น ๆ สามารถคิดในทำนองเดียวกัน

ดังนั้น คำตอบสุดท้ายคือ

$|H \cup T \cup U| = \sum\limits_{i=0}^{i=9} {h_i \choose 2} + \sum\limits_{i=0}^{i=9} {t_i \choose 2} + \sum\limits_{i=0}^{i=9} {u_i \choose 2} + \sum\limits_{i=00}^{i=99} {ht_i \choose 2} - \sum\limits_{i=00}^{i=99} {hu_i \choose 2} - \sum\limits_{i=00}^{i=99} {tu_i \choose 2} + \sum\limits_{i=000}^{i=999} {htu_i \choose 2}$