Gegeben sei ein Array von n nicht negativen ganzen Zahlen. Die Aufgabe besteht darin, die Summe des Produkts der Elemente aller möglichen Teilmengen zu ermitteln. Es kann davon ausgegangen werden, dass die Zahlen in Teilmengen klein sind und das Rechenprodukt keinen arithmetischen Überlauf verursacht.
Beispiel :
Input : arr[] = {1 2 3} Output : 23 Possible Subset are: 1 2 3 {1 2} {1 3} {2 3} {1 2 3} Products of elements in above subsets : 1 2 3 2 3 6 6 Sum of all products = 1 + 2 + 3 + 2 + 3 + 6 + 6 = 23 Naiver Ansatz: Ein einfacher Ansatz ist Generieren Sie alle möglichen Teilmengen nacheinander und berechne die Summe aller Elemente. Die zeitliche Komplexität dieses Ansatzes ist exponentiell, da es insgesamt 2 gibtN- 1 Teilmengen.
Ein Effizienter Ansatz besteht darin, das gesamte Problem in ein Muster zu verallgemeinern. Angenommen, wir haben zwei Zahlen a und b. Wir können alle möglichen Teilmengenprodukte wie folgt schreiben:
= a + b + ab = a(1+b) + b + 1 - 1 = a(1+b) + (1+b) - 1 = (a + 1) * (b + 1) - 1 = (1+a) * (1 + b) - 1
Nehmen Sie nun drei Zahlen a b c:-
= a + b + c + ab + bc + ca + abc = a + ac + b + bc + ab + abc + c + 1 - 1 = a(1+c) + b(1+c) + ab(1+c) + c + 1 - 1 = (a + b + ab + 1)(1+c) - 1 = (1+a) * (1+b) * (1+c) - 1
Das obige Muster kann für n Zahlen verallgemeinert werden.
Nachfolgend finden Sie die Umsetzung der obigen Idee:
C++// C++ program to find sum of product of // all subsets. #include
// Java program to find sum of product of // all subsets. public class Subset { // Returns sum of products of all subsets // of arr[0..n-1] static int productOfSubsetSums(int arr[] int n) { int ans = 1; for (int i = 0; i < n; ++i ) ans = ans * (arr[i] + 1); return ans-1; } public static void main (String[] args) { int arr[] = {1 2 3 4}; int n = arr.length; System.out.println(productOfSubsetSums(arr n)); } } // This code is contributed by Saket Kumar
# Python3 program to # find sum of product of # all subsets. # Returns sum of products # of all subsets # of arr[0..n-1] def productOfSubsetSums(arr n): ans = 1; for i in range(0n): ans = ans * (arr[i] + 1) return ans-1 # Driver code arr = [1 2 3 4] n = len(arr) print (productOfSubsetSums(arr n)) # This code is contributed # by Shreyanshi Arun.
// C# program to find sum of // product of all subsets. using System; public class Subset { // Returns sum of products of all // subsets of arr[0..n-1] static int productOfSubsetSums(int []arr int n) { int ans = 1; for (int i = 0; i < n; ++i ) ans = ans * (arr[i] + 1); return ans-1; } // Driver Code public static void Main () { int []arr = {1 2 3 4}; int n = arr.Length; Console.Write(productOfSubsetSums(arr n)); } } // This code is contributed by Nitin Mittal.
// PHP program to find sum of // product of all subsets. // Returns sum of products of // all subsets of arr[0..n-1] function productOfSubsetSums($arr $n) { $ans = 1; for ($i = 0; $i < $n; ++$i ) $ans = $ans * ($arr[$i] + 1); return $ans-1; } // Driver code $arr = array(1 2 3 4); $n = sizeof($arr); echo(productOfSubsetSums($arr $n)); // This code is contributed by Ajit. ?> <script> // Javascript program to find sum of product of // all subsets. // Returns sum of products of all subsets // of arr[0..n-1] function productOfSubsetSums(arr n) { let ans = 1; for (let i = 0; i < n; ++i ) ans = ans * (arr[i] + 1); return ans-1; } // Driver code let arr = [1 2 3 4]; let n = arr.length; document.write(productOfSubsetSums(arr n)); // This code is contributed by Mayank Tyagi </script>
Ausgabe
119
Zeitkomplexität: O(n)
Hilfsraum: O(1)
Quiz erstellen