ในปัญหานี้ ให้อาร์เรย์ N จำนวนเต็ม ต้องหาจำนวน Subsequence ที่คูณสมาชิกแล้วได้เลขที่เป็นกำลังสอง
ตัวอย่าง
Input − arr = [2, 5, 4]
Output − 3
คำอธิบาย − Subsequence ที่ได้: [2], [4], [2, 4]
ข้อสังเกตสำคัญ
เฉพาะตัวเลขที่เป็นกำลังสองเท่านั้น ที่คูณกันแล้วจะได้กำลังสอง (เพราะกำลังสอง × กำลังสอง = กำลังสอง)
ดังนั้น ให้นับจำนวน M = จำนวนสมาชิกในอาร์เรย์ที่เป็นกำลังสอง
จำนวน Subsequence ที่เป็นไปได้ = 2ᴹ - 1 (ลบ 1 เพราะไม่นับ empty subsequence)
การตรวจสอบว่าเป็นกำลังสอง
เลข n เป็นกำลังสองก็ต่อเมื่อ n & (n-1) == 0 (และ n > 0)
ตัวอย่างโค้ด C++
#include <iostream>
#include <math.h>
using namespace std;
bool isPowerTwo(int num) {
if (num == 0) return false;
if (num == 1) return true;
if (num & (num - 1)) return false; // มีบิต 1 มากกว่า 1 ตัว
return true;
}
int SubsequenceWithPowerTwo(int arr[], int N) {
int count = 0;
for (int i = 0; i < N; i++)
if (isPowerTwo(arr[i]))
count++;
return (int)(pow(2, count)) - 1;
}
int main() {
int arr[] = {5, 4, 8, 12, 32, 9};
int N = sizeof(arr)/sizeof(arr[0]);
cout << "No. of subsequences which multiply to a power of 2 are : ";
cout << SubsequenceWithPowerTwo(arr, N) << endl;
return 0;
}
ผลลัพธ์
No. of subsequences which multiply to a number which is a power of 2 are : 7
คำอธิบาย
ในอาร์เรย์ มีตัวที่เป็นกำลังสอง: 4, 8, 32 (3 ตัว)
จำนวน Subsequence = 2³ - 1 = 7
