Duotas n neneigiamų sveikųjų skaičių masyvas. Užduotis – rasti visų galimų poaibiu elementų sandaugos sumą. Galima daryti prielaidą, kad skaičiai poaibiuose yra maži ir skaičiavimo sandauga nesukelia aritmetinio perpildymo.
Pavyzdys:
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 Naivus požiūris: Paprastas požiūris yra generuoti visus galimus poaibius po vieną ir apskaičiuokite visų elementų sumą. Laikas Šio metodo sudėtingumas yra eksponentinis, nes iš viso yra 2n- 1 poaibis.
An Efektyvus požiūris yra apibendrinti visą problemą į tam tikrą modelį. Tarkime, kad turime du skaičius a ir b. Mes galime parašyti visus galimus pogrupio produktus kaip: -
= 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
Dabar paimkite tris skaičius 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
Aukščiau pateiktą modelį galima apibendrinti n skaičių.
Žemiau yra aukščiau pateiktos idėjos įgyvendinimas:
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>
Išvestis
119
Laiko sudėtingumas: O(n)
Pagalbinė erdvė: O(1)
Sukurti viktoriną