# Sum of cubes of all Subsets of given Array

Given an array **arr[]**, the task is to calculate the sum of cubes of all possible non-empty subsets of the given array. Since, the answer can be large, print the value as **mod** 1000000007.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:arr[] = {1, 2}Output:18

subset({1}) = 1^{3}= 1

subsetval({2}) = 2^{3}= 8

subset({1, 2}) = 1^{3}+ 2^{3}= 1 + 8 = 9

Sum of cubes of all Subsets = 1 + 8 + 9 = 18

Input:arr[] = {1, 1, 1}Output:12

**Naive approach:** A simple approach is to find all the subset and then cube each element in that subset and add it to the result. The time complexity of this approach will be **O(2 ^{N})**

**Efficient approach:**

- It can be observed that each element of the original array appears in 2
^{(N – 1)}times in all subsets. - Therefore contribution of any element
**arr**in the final answer will be_{i}arr

_{i}* 2^{(N – 1)} - So, the Sum of cubes of all Subsets will be
[arr

_{0}^{3}+ arr_{1}^{3}+ arr_{2}^{3}+ … + arr_{(N-1)}^{3}] * 2^{(N – 1)}

Below is the implementation of the above approach:

## C++

`// C++ implementation of the approach` ` ` `#include <bits/stdc++.h>` `using` `namespace` `std;` ` ` `const` `int` `mod = 1e9 + 7;` ` ` `// Function to return (2^P % mod)` `long` `long` `power(` `int` `p)` `{` ` ` `long` `long` `res = 1;` ` ` `for` `(` `int` `i = 1; i <= p; ++i) {` ` ` `res *= 2;` ` ` `res %= mod;` ` ` `}` ` ` `return` `res % mod;` `}` ` ` `// Function to return` `// the sum of cubes of subsets` `long` `long` `subset_cube_sum(vector<` `int` `>& A)` `{` ` ` ` ` `int` `n = (` `int` `)A.size();` ` ` ` ` `long` `long` `ans = 0;` ` ` ` ` `// cubing the elements` ` ` `// and adding it to ans` ` ` `for` `(` `int` `i : A) {` ` ` `ans += (1LL * i * i * i) % mod;` ` ` `ans %= mod;` ` ` `}` ` ` ` ` `return` `(1LL * ans * power(n - 1))` ` ` `% mod;` `}` ` ` `// Driver code` `int` `main()` `{` ` ` `vector<` `int` `> A = { 1, 2 };` ` ` ` ` `cout << subset_cube_sum(A);` ` ` ` ` `return` `0;` `}` |

## Python3

`# Python3 implementation of the approach ` `mod ` `=` `int` `(` `1e9` `) ` `+` `7` `; ` ` ` `# Function to return (2^P % mod) ` `def` `power(p) :` ` ` ` ` `res ` `=` `1` `; ` ` ` `for` `i ` `in` `range` `(` `1` `, p ` `+` `1` `) :` ` ` `res ` `*` `=` `2` `; ` ` ` `res ` `%` `=` `mod; ` ` ` ` ` `return` `res ` `%` `mod; ` ` ` `# Function to return ` `# the sum of cubes of subsets ` `def` `subset_cube_sum(A) : ` ` ` ` ` `n ` `=` `len` `(A); ` ` ` ` ` `ans ` `=` `0` `; ` ` ` ` ` `# cubing the elements ` ` ` `# and adding it to ans ` ` ` `for` `i ` `in` `A :` ` ` `ans ` `+` `=` `(i ` `*` `i ` `*` `i) ` `%` `mod; ` ` ` `ans ` `%` `=` `mod; ` ` ` ` ` `return` `(ans ` `*` `power(n ` `-` `1` `)) ` `%` `mod; ` ` ` `# Driver code ` `if` `__name__ ` `=` `=` `"__main__"` `: ` ` ` ` ` `A ` `=` `[ ` `1` `, ` `2` `]; ` ` ` ` ` `print` `(subset_cube_sum(A)); ` ` ` `# This code is contributed by Yash_R` |

**Output:**

18

**Time Complexity:** O(N)