ปัญหา
กำหนดอาร์เรย์ จำนวนเต็ม หาจำนวนกลุ่ม (Groups) ขนาด 2 หรือ 3 ที่ ผลรวมหาร 3 ลงตัว
ตัวอย่าง: [3, 6, 7, 2, 9] → 8 กลุ่ม
แนวคิด: Modulo 3 Classification
จำนวนเต็มทุกตัว mod 3 จะได้แค่ 0, 1, 2
นับจำนวนในแต่ละกลุ่ม: c[0], c[1], c[2]
กลุ่มขนาด 2 (Pairs)
(0,0):C(c[0], 2) = c[0]*(c[0]-1)/2(1,2):c[1] * c[2]
กลุ่มขนาด 3 (Triplets)
(0,0,0):C(c[0], 3) = c[0]*(c[0]-1)*(c[0]-2)/6(1,1,1):C(c[1], 3)(2,2,2):C(c[2], 3)(0,1,2):c[0] * c[1] * c[2]
โค้ด C++
#include <bits/stdc++.h>
using namespace std;
int countGroups(int arr[], int n) {
int c[3] = {0};
for (int i = 0; i < n; i++) {
c[arr[i] % 3]++;
}
int res = 0;
// Pairs
res += (c[0] * (c[0] - 1)) / 2; // (0,0)
res += c[1] * c[2]; // (1,2)
// Triplets
res += (c[0] * (c[0] - 1) * (c[0] - 2)) / 6; // (0,0,0)
res += (c[1] * (c[1] - 1) * (c[1] - 2)) / 6; // (1,1,1)
res += (c[2] * (c[2] - 1) * (c[2] - 2)) / 6; // (2,2,2)
res += c[0] * c[1] * c[2]; // (0,1,2)
return res;
}
int main() {
int arr[] = {3, 6, 7, 2, 9};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Required number of groups are " << countGroups(arr, n) << endl; // 8
return 0;
}
การทำงานตัวอย่าง
Array: [3, 6, 7, 2, 9]
Mod 3: [0, 0, 1, 2, 0]
c[0]=3 (3,6,9), c[1]=1 (7), c[2]=1 (2)
Pairs:
(0,0): C(3,2) = 3 → (3,6), (3,9), (6,9)
(1,2): 1×1 = 1 → (7,2)
Total pairs = 4
Triplets:
(0,0,0): C(3,3) = 1 → (3,6,9)
(0,1,2): 3×1×1 = 3 → (3,7,2), (6,7,2), (9,7,2)
Total triplets = 4
Grand Total = 8
ความซับซ้อน
- Time: O(n)
- Space: O(1)
Input / Output
Input: [3, 6, 7, 2, 9]
Output: 8
