# Sum of product of all subsets formed by only divisors of N

Given a number **N**, the task is to find the sum of the product of elements of all the possible subsets formed by only divisors of **N**.**Examples:**

Input:N = 3Output:7Explanation:

Divisors of 3 are 1 and 3. All possible subsets are {1}, {3}, {1, 3}.

Therefore, the sum of the product of all possible subsets are:

(1 + 3 + (1 * 3)) = 7.Input:N = 4Output:29Explanation:

Divisors of 4 are 1, 2 and 4. All possible subsets are {1}, {2}, {4}, {1, 2}, {1, 4}, {2, 4}, {1, 2, 4}.

Therefore, the sum of the product of all possible subsets are:

(1 + 2 + 4 + (1 * 2) + (1 * 4) + (2 * 4) + (1 * 2 * 4)) = 29.

**Naive Approach:** The naive approach for this problem is to generate all possible subsets from its divisors and then calculate the product of each of the subset. After calculating the product of every subset, add all the products to find the required answer. The time complexity for this approach is **O(2 ^{D})** where D is the number of divisors of N.

**Efficient Approach:**The idea behind the efficient approach comes from the following observation:

Let x and y is the divisor of N. Then sum of product of all subsets will be = x + y + x * y = x(1 + y) + y + 1 - 1 = x(1 + y) + (1 + y) - 1 = (x + 1) * (y + 1) - 1 = (1 + x) * (1 + y) - 1 Now let take three divisors x, y, z. Then sum of product of all subsets will be = x + y + z + xy + yz + zx + xyz = x + xz + y + yz + xy + xyz + z + 1 - 1 = x(1 + z) + y(1 + z) + xy(1 + z) + z + 1 - 1 = (x + y + xy + 1) * (1 + z) - 1 = (1 + x) * (1 + y) * (1 + z) - 1

Clearly, from the above observation, we can conclude that if **{D _{1}, D_{2}, D_{3}, … D_{n}}** are the divisors of N then the required answer will be:

(D_{1}+ 1) * (D_{2}+ 1) * (D_{3}+ 1) * ... (D_{n}+ 1)

Below is the implementation of the above approach:

## C++

`// C++ program to find the sum of` `// product of all the subsets` `// formed by only divisors of N` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find the sum of` `// product of all the subsets` `// formed by only divisors of N` `int` `GetSum(` `int` `n)` `{` ` ` `// Vector to store all the` ` ` `// divisors of n` ` ` `vector<` `int` `> divisors;` ` ` `// Loop to find out the` ` ` `// divisors of N` ` ` `for` `(` `int` `i = 1; i * i <= n; i++) {` ` ` `if` `(n % i == 0) {` ` ` `// Both 'i' and 'n/i' are the` ` ` `// divisors of n` ` ` `divisors.push_back(i);` ` ` `// Check if 'i' and 'n/i' are` ` ` `// equal or not` ` ` `if` `(i != n / i) {` ` ` `divisors.push_back(n / i);` ` ` `}` ` ` `}` ` ` `}` ` ` `int` `ans = 1;` ` ` `// Calculating the answer` ` ` `for` `(` `auto` `i : divisors) {` ` ` `ans *= (i + 1);` ` ` `}` ` ` `// Excluding the value` ` ` `// of the empty set` ` ` `ans = ans - 1;` ` ` `return` `ans;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 4;` ` ` `cout << GetSum(N) << endl;` `}` |

## Java

`// Java program to find the sum of product` `// of all the subsets formed by only` `// divisors of N` `import` `java.util.*;` `class` `GFG {` `// Function to find the sum of product` `// of all the subsets formed by only` `// divisors of N` `static` `int` `GetSum(` `int` `n)` `{` ` ` `// Vector to store all the` ` ` `// divisors of n` ` ` `Vector<Integer> divisors = ` `new` `Vector<Integer>(); ` ` ` `// Loop to find out the` ` ` `// divisors of N` ` ` `for` `(` `int` `i = ` `1` `; i * i <= n; i++)` ` ` `{` ` ` `if` `(n % i == ` `0` `)` ` ` `{` ` ` ` ` `// Both 'i' and 'n/i' are the` ` ` `// divisors of n` ` ` `divisors.add(i);` ` ` ` ` `// Check if 'i' and 'n/i' are` ` ` `// equal or not` ` ` `if` `(i != n / i)` ` ` `{` ` ` `divisors.add(n / i);` ` ` `}` ` ` `}` ` ` `}` ` ` `int` `ans = ` `1` `;` ` ` `// Calculating the answer` ` ` `for` `(` `int` `i = ` `0` `; i < divisors.size(); i++)` ` ` `{` ` ` `ans *= (divisors.get(i) + ` `1` `);` ` ` `}` ` ` `// Excluding the value` ` ` `// of the empty set` ` ` `ans = ans - ` `1` `;` ` ` `return` `ans;` `}` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `N = ` `4` `;` ` ` `System.out.println(GetSum(N));` `}` `}` `// This code is contributed by offbeat` |

## Python3

`# Python3 program to find the sum of` `# product of all the subsets` `# formed by only divisors of N` `# Function to find the sum of` `# product of all the subsets` `# formed by only divisors of N` `def` `GetSum(n):` ` ` `# Vector to store all the` ` ` `# divisors of n` ` ` `divisors ` `=` `[]` ` ` `# Loop to find out the` ` ` `# divisors of N` ` ` `i ` `=` `1` ` ` `while` `i ` `*` `i <` `=` `n :` ` ` `if` `(n ` `%` `i ` `=` `=` `0` `):` ` ` `# Both 'i' and 'n/i' are the` ` ` `# divisors of n` ` ` `divisors.append(i)` ` ` `# Check if 'i' and 'n/i' are` ` ` `# equal or not` ` ` `if` `(i !` `=` `n ` `/` `/` `i):` ` ` `divisors.append(n ` `/` `/` `i)` ` ` ` ` `i ` `+` `=` `1` ` ` `ans ` `=` `1` ` ` `# Calculating the answer` ` ` `for` `i ` `in` `divisors:` ` ` `ans ` `*` `=` `(i ` `+` `1` `)` ` ` `# Excluding the value` ` ` `# of the empty set` ` ` `ans ` `=` `ans ` `-` `1` ` ` `return` `ans` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` ` ` `N ` `=` `4` ` ` `print` `(GetSum(N))` `# This code is contributed by chitranayal` |

## C#

`// C# program to find the sum of product` `// of all the subsets formed by only` `// divisors of N` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG{` `// Function to find the sum of product` `// of all the subsets formed by only` `// divisors of N` `static` `int` `GetSum(` `int` `n)` `{` ` ` `// Store all the` ` ` `// divisors of n` ` ` `List<` `int` `> divisors = ` `new` `List<` `int` `>();` ` ` `// Loop to find out the` ` ` `// divisors of N` ` ` `for` `(` `int` `i = 1; i * i <= n; i++)` ` ` `{` ` ` `if` `(n % i == 0)` ` ` `{` ` ` ` ` `// Both 'i' and 'n/i' are the` ` ` `// divisors of n` ` ` `divisors.Add(i);` ` ` ` ` `// Check if 'i' and 'n/i' are` ` ` `// equal or not` ` ` `if` `(i != n / i)` ` ` `{` ` ` `divisors.Add(n / i);` ` ` `}` ` ` `}` ` ` `}` ` ` `int` `ans = 1;` ` ` `// Calculating the answer` ` ` `foreach` `(` `int` `i ` `in` `divisors)` ` ` `{` ` ` `ans *= (i + 1);` ` ` `}` ` ` `// Excluding the value` ` ` `// of the empty set` ` ` `ans = ans - 1;` ` ` `return` `ans;` `}` `// Driver code` `public` `static` `void` `Main()` `{` ` ` `int` `N = 4;` ` ` `Console.WriteLine(GetSum(N));` `}` `}` `// This code is contributed by sanjoy_62` |

## Javascript

`<script>` `// Javascript program to find the sum of` `// product of all the subsets` `// formed by only divisors of N` `// Function to find the sum of` `// product of all the subsets` `// formed by only divisors of N` `function` `GetSum(n)` `{` ` ` `// Vector to store all the` ` ` `// divisors of n` ` ` `var` `divisors = [];` ` ` `// Loop to find out the` ` ` `// divisors of N` ` ` `for` `(` `var` `i = 1; i * i <= n; i++) {` ` ` `if` `(n % i == 0) {` ` ` `// Both 'i' and 'n/i' are the` ` ` `// divisors of n` ` ` `divisors.push(i);` ` ` `// Check if 'i' and 'n/i' are` ` ` `// equal or not` ` ` `if` `(i != n / i) {` ` ` `divisors.push(n / i);` ` ` `}` ` ` `}` ` ` `}` ` ` `var` `ans = 1;` ` ` `// Calculating the answer` ` ` `for` `(` `var` `i =0; i< divisors.length; i++)` ` ` `{` ` ` `ans *= (divisors[i]+1);` ` ` `}` ` ` `// Excluding the value` ` ` `// of the empty set` ` ` `ans = ans - 1;` ` ` `return` `ans;` `}` `// Driver Code` `var` `N = 4;` `document.write( GetSum(N));` `// This code is contributed by noob2000.` `</script>` |

**Output:**

29

**Time Complexity:** *O(sqrt(N))*, where N is the given number.

**Auxiliary Space: **O(sqrt(N))