ในปัญหานี้ เราจะได้รับอาร์เรย์จำนวนเต็ม N งานของเราคือการหาจำนวนลำดับที่ตามมาที่สามารถเกิดขึ้นได้ โดยที่หากองค์ประกอบของพวกมันถูกคูณ ก็จะได้ผลลัพธ์เป็นจำนวนที่เป็นกำลังสอง
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล − arr =[2, 5, 4]
ผลผลิต − 3
คำอธิบาย − ลำดับถัดมา [2], [4] และ [2, 4] ให้ผลลัพธ์ที่ต้องการ
เพื่อแก้ปัญหานี้ เราต้องเข้าใจตรรกะของอำนาจ
เฉพาะตัวเลขที่มีกำลัง 2 เท่านั้นที่จะคูณเพื่อให้ได้ผลลัพธ์ที่ต้องการ ดังนั้น เราต้องพิจารณาเฉพาะส่วนต่อจากอาร์เรย์ที่ตัวเองมีกำลัง 2
ดังนั้น หากในอาร์เรย์มีองค์ประกอบ M ที่มีกำลัง 2 การนับอาร์เรย์ย่อยจะเป็น 2 M - 1
ตัวอย่าง
โปรแกรมแสดงการใช้งานโซลูชันของเรา
#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;
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 number which is 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
