ได้รับอาร์เรย์ 4 ชุด ต้องการหาจำนวนควอดรูเพลต (4 ตัวเลข) ที่แต่ละตัวมาจากอาร์เรย์ต่างกัน และผลรวมเท่ากับค่า Sum ที่กำหนด
ตัวอย่าง
อินพุต:
A[] = {1, 3, 1}, B[] = {2, 4, 5}, C[] = {1, 1, 2}, D[] = {4, 4, 0}, Sum = 5
เอาต์พุต: 2
คำอธิบาย: 2 ควอดรูเพลต: (1,2,2,0) จาก A[0],B[0],C[2],D[2] และ (1,2,2,0) จาก A[2],B[0],C[2],D[2]
อินพุต: ทุกอาร์เรย์เป็น {1,1,1}, Sum = 3
เอาต์พุต: 0 (ผลรวมทุกควอดรูเพลตคือ 4 > 3)
แนวทางการแก้ปัญหา
- ใช้ลูป
forซ้อนกัน 4 ชั้น สำหรับแต่ละอาร์เรย์ - ลูปนอกสุด
iสำหรับfirst[], ตามด้วยjสำหรับsecond[],kสำหรับthird[],lสำหรับfourth[] - ตรวจสอบ
first[i] + second[j] + third[k] + fourth[l] == sumถ้าใช่เพิ่มตัวนับ - ซับซ้อนเวลา O(n⁴) เหมาะกับอาร์เรย์ขนาดเล็ก
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
int quadruplets(int first[], int second[], int third[], int fourth[],
int first_size, int second_size, int third_size, int fourth_size, int sum) {
int count = 0;
for (int i = 0; i < first_size; i++) {
for (int j = 0; j < second_size; j++) {
for (int k = 0; k < third_size; k++) {
for (int l = 0; l < fourth_size; l++) {
if (first[i] + second[j] + third[k] + fourth[l] == sum) {
count++;
}
}
}
}
}
return count;
}
int main() {
int first[] = {7, -8};
int second[] = {7, -2};
int third[] = {4, -2};
int fourth[] = {3, -4};
int first_size = sizeof(first) / sizeof(first[0]);
int second_size = sizeof(second) / sizeof(second[0]);
int third_size = sizeof(third) / sizeof(third[0]);
int fourth_size = sizeof(fourth) / sizeof(fourth[0]);
int sum = 0;
cout << "Count of quadruplets with given sum are: " << quadruplets(first, second, third, fourth,
first_size, second_size, third_size, fourth_size, sum);
return 0;
}
ผลลัพธ์
Count of quadruplets with given sum are: 1
