इस समस्या में, हमें N पूर्णांकों की एक सरणी दी गई है। हमारा काम उन अनुक्रमों की गिनती ज्ञात करना है जो इस तरह बन सकते हैं कि यदि उनके तत्वों को गुणा किया जाए, तो वे एक संख्या में परिणामित होते हैं जो दो की शक्ति है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट - गिरफ्तारी =[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