0

Given an array A with size N. Value of a subset of Array A is defined as product of all numbers in that subset. We have to return the product of values of all possible non-empty subsets of array A %(10^9+7).

E.G. array A {3,5}

` Value{3} = 3, Value{5} = 5, Value{3,5} = 5*3 = 15

answer = 3*5*15 %(10^9+7).

Can someone explain the mathematics behind the problem. I am thinking of solving it by combination to solve it efficiently.

I have tried using brute force it gives correct answer but it is way too slow. Next approach is using combination. Now i think that if we take all the sets and multiply all the numbers in those set then we will get the correct answer. Thus i have to find out how many times a number is coming in calculation of answer. In the example 5 and 3 both come 2 times. If we look closely, each number in a will come same number of times.

Ayush Gupta
  • 37
  • 1
  • 6
  • 2
    If you want help with the math, then please go to [the Math SE site](https://math.stackexchange.com/tour). Once you understand the math behind the problem and have problems with your attempt of implementing it then you're more than welcome back here to ask for help with the code. – Some programmer dude Jul 29 '19 at 12:13
  • I do not fully understand. Can you please add a linke to the original question on hackerearth or codechef or somewhere. Thanks – A M Jul 29 '19 at 12:25
  • It was in a test and now the link is not active. – Ayush Gupta Jul 29 '19 at 15:51

3 Answers3

3

You're heading in the right direction.

Let x be an element of the given array A. In our final answer, x appears p number of times, where p is equivalent to the number of subsets of A possible that include x.

How to calculate p? Once we have decided that we will definitely include x in our subset, we have two choices for the rest N-1 elements: either include them in set or do not. So, we conclude p = 2^(N-1).

So, each element of A appears exactly 2^(N-1) times in the final product. All remains is to calculate the answer: (a1 * a2 * ... * an)^p. Since the exponent is very large, you can use binary exponentiation for fast calculation.

As Matt Timmermans suggested in comments below, we can obtain our answer without actually calculating p = 2^(N-1). We first calculate the product a1 * a2 * ... * an. Then, we simply square this product n-1 times.

The corresponding code in C++:

int func(vector<int> &a) {
    int n = a.size();
    int m = 1e9+7;
    if(n==0) return 0;
    if(n==1) return (m + a[0]%m)%m;

    long long ans = 1;

    //first calculate ans = (a1*a2*...*an)%m
    for(int x:a){
        //negative sign does not matter since we're squaring
        if(x<0) x *= -1;
        x %= m;
        ans *= x;
        ans %= m;
    }

    //now calculate ans = [ ans^(2^(n-1)) ]%m
    //we do this by squaring ans n-1 times
    for(int i=1; i<n; i++){
        ans = ans*ans;
        ans %= m;
    }

    return (int)ans;
}
mrpandey
  • 627
  • 2
  • 9
  • 17
  • 2
    Note that the exponent is too big to fit into a normal integer type, but its bits have a very simple pattern, so you can do the exponentiation without actually creating the exponent. – Matt Timmermans Jul 29 '19 at 12:33
0

Let, A={a,b,c}
All possible subset of A is ={{},{a},{b},{c},{a,b},{b,c},{c,a},{a,b,c,d}}
Here number of occurrence of each of the element are 4 times.
So if A={a,b,c,d}, then numbers of occurrence of each of the element will be 2^3.
So if the size of A is n, number of occurrence of eachof the element will be 2^(n-1)

So final result will be = a1^p*a2^pa3^p....*an^p
where p is 2^(n-1)

We need to solve x^2^(n-1) % mod.

We can write x^2^(n-1) % mod as x^(2^(n-1) % phi(mod)) %mod . link
As mod is a prime then phi(mod)=mod-1.

So at first find p= 2^(n-1) %(mod-1).
Then find Ai^p % mod for each of the number and multiply with the final result.

mahbubcseju
  • 2,200
  • 2
  • 16
  • 21
  • I got the same answer after taking some numbers. What i was looking for is a derivation or explanation so that i can solve similar problems. – Ayush Gupta Jul 29 '19 at 15:57
0

I read the previous answers and I was understanding the process of making sets. So here I am trying to put it in as simple as possible for people so that they can apply it to similar problems.

Let i be an element of array A. Following the approach given in the question, i appears p number of times in final answer.

Now, how do we make different sets. We take sets containing only one element, then sets containing group of two, then group of 3 ..... group of n elements. Now we want to know for every time when we are making set of certain numbers say group of 3 elements, how many of these sets contain i? There are n elements so for sets of 3 elements which always contains i, combinations are (n-1)C(3-1) because from n-1 elements we can chose 3-1 elements. if we do this for every group, p = [ (n-1)C(x-1) ] , m going from 1 to n. Thus, p= 2^(n-1).

Similarly for every element i, p will be same. Thus we get final answer= A[0]^p *A[1]^p...... A[n]^p

Ayush Gupta
  • 37
  • 1
  • 6