จากอาร์เรย์ เราต้องหาจำนวนคู่ที่ผลรวมเป็นกำลัง 2 มาดูตัวอย่างกัน
ป้อนข้อมูล
arr = [1, 2, 3]
ผลผลิต
1
มีเพียงคู่เดียวที่ผลรวมเป็นกำลัง 2 และทั้งคู่คือ (1, 3)
อัลกอริทึม
- เริ่มต้นอาร์เรย์ด้วยตัวเลขสุ่ม
- เริ่มต้นการนับเป็น 0
- เขียนสองลูปเพื่อให้ได้คู่ของอาร์เรย์ทั้งหมด
- คำนวณผลรวมของทุกคู่
- ตรวจสอบว่าผลรวมเป็นกำลัง 2 หรือไม่โดยใช้ AND
- เพิ่มการนับถ้าการนับเป็นยกกำลัง 2
- คืนการนับ
การนำไปใช้
ต่อไปนี้เป็นการนำอัลกอริธึมข้างต้นไปใช้ใน C++
#include <bits/stdc++.h>
using namespace std;
int get2PowersCount(int arr[], int n) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int sum = arr[i] + arr[j];
if ((sum & (sum - 1)) == 0) {
count++;
}
}
}
return count;
}
int main() {
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int n = 10;
cout << get2PowersCount(arr, n) << endl;
return 0;
} ผลลัพธ์
หากคุณเรียกใช้โค้ดด้านบน คุณจะได้ผลลัพธ์ดังต่อไปนี้
6
