इस समस्या में, हमें N संख्याओं का एक ऐरे arr[] दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो सभी संभावित सबसेट के गुणनफल का योग निकालेगा।
यहां, हम सभी सबसेट ढूंढेंगे और फिर प्रत्येक सबसेट के लिए सभी तत्वों का गुणनफल निकालेंगे। फिर अंतिम योग की गणना करने के लिए सभी मानों को जोड़ेंगे।
उदाहरण से समझते हैं
इनपुट
arr[] = {4, 5, 6}आउटपुट
209
व्याख्या
arr[] के सभी सबसेट हैं: {4}, {5}, {6}, {4, 5}, {5, 6}, {4, 6}, {4, 5, 6}
गुणनफल का योग = (4) + (5) + (6) + (4*5) + (5*6) + (4*6) + (4*5*6)
= (4) + (5) + (6) + (20) + (30) + (24) + (120)
= 209समस्या को हल करने का एक सरल दृष्टिकोण सेट के सभी सबसेट ढूंढना और प्रत्येक सेट के तत्वों का गुणनफल निकालना है। और सभी गुणनफलों को जोड़ना, फिर अंतिम योग वापस करना जब सभी सबसेट ट्रैवर्स हो जाएं।
C++ प्रोग्राम उदाहरण (सरल दृष्टिकोण)
#include <iostream>
#include <math.h>
using namespace std;
int findSumProductSubset(int *arr, int set_length) {
unsigned int size = pow(2, set_length);
int sum = 0;
int product;
for (int counter = 1; counter < size; counter++) {
product = 1;
for (int j = 0; j < size; j++) {
if (counter & (1 << j))
product *= arr[j];
}
sum += product;
}
return sum;
}
int main() {
int arr[] = {4, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The sum of the product of all subsets is " << findSumProductSubset(arr, n);
}आउटपुट
The sum of the product of all subsets is 209
उपरोक्त दृष्टिकोण सभी सबसेट उत्पन्न करता है इसलिए इसकी समय जटिलता एक्सपोनेंशियल है। इसलिए, यह सबसे कुशल दृष्टिकोण नहीं है।
कुशल दृष्टिकोण: समाधान के लिए पैटर्न ढूंढना
अब, तीन संख्याओं x, y, z का एक सेट देखते हैं।
योग = x + y + z + xy + yz + xz + xyz
योग = x + xz + y + yz + xy + xyz + z + 1 - 1
योग = x(1+z) + y(1+z) + xy(1+z) + 1(z+1) - 1
योग = (x + y + xy + 1)(1 + z) - 1
योग = (x(1+y) + 1(1+y))(1+z) - 1
योग = (1 + x) * (1 + y) * (1 + z) - 1
इसे निम्न तरीके से सामान्यीकृत किया जा सकता है,
n तत्व सेट के लिए,
योग = (1+ e1) * (1 + e2) * … * (1 + en) - 1
C++ प्रोग्राम उदाहरण (कुशल दृष्टिकोण)
#include <iostream>
using namespace std;
int productOfSubsetSums(int arr[], int n) {
int sum = 1;
for (int i = 0; i < n; ++i)
sum *= (arr[i] + 1);
sum--;
return sum;
}
int main() {
int arr[] = {5, 6, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Sum of product of all possible subsets is " << productOfSubsetSums(arr, n);
return 0;
}आउटपुट
Sum of product of all possible subsets is 3779