Sum of the products of all possible Subsets

https://www.geeksforgeeks.org/sum-products-possible-subsets/

Given an array of n non-negative integers. The task is to find the sum of the product of elements of all the possible subsets. It may be assumed that the numbers in subsets are small and computing product doesn’t cause arithmetic overflow.

Example :

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

An Efficient approach is to generalize the whole problem into some pattern. Suppose we have two numbers a and b. We can write all possible subset products as:-

   = 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

Now take three numbers 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  

The above pattern can be generalized for n numbers.

    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;

    }      

Given a set, find XOR of the XOR’s of all subsets.

https://www.geeksforgeeks.org/given-a-set-find-xor-of-the-xors-of-all-subsets/

The question is to find XOR of the XOR’s of all subsets. i.e if the set is {1,2,3}. All subsets are : [{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}]. Find the XOR of each of the subset and then find the XOR of every subset result.

This is a very simple question to solve if we get the first step (and only step) right. The solution is XOR is always 0 when n > 1 and Set[0] when n is 1.

The logic goes simple. Let us consider n’th element, it can be included in all subsets of remaining (n-1) elements. The number of subsets for (n-1) elements is equal to 2(n-1) which is always even when n>1. Thus, in the XOR result, every element is included even number of times and XOR of even occurrences of any number is 0.

static int findXOR(int Set[], int n) {

      

    // XOR is 1 only when n is 1, else 0

    if (n == 1)

    return Set[0];

    else

    return 0;

}




Sum of all Subarrays

https://www.geeksforgeeks.org/sum-of-all-subarrays/

Given an integer array ‘arr[]’ of size n, find sum of all sub-arrays of given array.

Examples :

Input   : arr[] = {1, 2, 3}
Output  : 20
Explanation : {1} + {2} + {3} + {2 + 3} + 
              {1 + 2} + {1 + 2 + 3} = 20

Method 2 (efficient solution)
If we take a close look then we observe a pattern. Let take an example

arr[] = [1, 2, 3], n = 3
All subarrays :  [1], [1, 2], [1, 2, 3], 
                 [2], [2, 3], [3]
here first element 'arr[0]' appears 3 times    
     second element 'arr[1]' appears 4 times  
     third element 'arr[2]' appears 3 times

Every element arr[i] appears in two types of subsets:
i)  In sybarrays beginning with arr[i]. There are 
    (n-i) such subsets. For example [2] appears
    in [2] and [2, 3].
ii) In (n-i)*i subarrays where this element is not
    first element. For example [2] appears in 
    [1, 2] and [1, 2, 3].

Total of above (i) and (ii) = (n-i) + (n-i)*i 
                            = (n-i)(i+1)
                                  
For arr[] = {1, 2, 3}, sum of subarrays is:
  arr[0] * ( 0 + 1 ) * ( 3 - 0 ) + 
  arr[1] * ( 1 + 1 ) * ( 3 - 1 ) +
  arr[2] * ( 2 + 1 ) * ( 3 - 2 ) 

= 1*3 + 2*4 + 3*3 
= 20

    public static long SubArraySum( int arr[] , int n )

    {

        long result = 0;

       

        // computing sum of subarray using formula

        for (int i=0; i<n; i++)

            result += (arr[i] * (i+1) * (n-i));

       

        // return all subarray sum

        return result ;

    }

Method 1 (Simple Solution)

Time Complexity : O(n3)

A simple solution is to generate all sub-array and compute their sum.

    public static long SubArraySum(int arr[], int n)

    {

        long result = 0;

       

        // Pick starting point

        for (int i = 0; i < n; i ++)

        {

            // Pick ending point

            for (int j = i; j < n; j ++)

            {

                // sum subarray between current

                // starting and ending points

                for (int k = i; k <= j; k++)

                    result += arr[k] ;

            }

        }

        return result ;

    }




https://www.geeksforgeeks.org/sum-of-all-subsequences-of-an-array/

Given an array of n integers. Find the sum of all possible subarrays.

Examples :

Input : arr[] = { 1, 2 }
Output : 6
All possible subarrays are {}, {1}, {2} 
and { 1, 2 }

Let us take a closer look at the problem and try to find a pattern

Let a[] = { 1, 2, 3 }

All subarrays are {}, {1}, {2}, {3}, {1, 2}, 
                     {1, 3}, {2, 3}, {1, 2, 3}

So sum of subarrays are 0 + 1 + 2 + 3 + 3 + 
                             4 + 5 + 8 = 24

Here we can observe that in sum every elements 
occurs 4 times. Or in general every element 
will occur 2^(n-1) times. And we can also 
observe that sum of array elements is 6. So
final result will be 6*4.

In general we can find sum of all subarrays by adding all elements of array multiplied by 2(n-1) where n is number of elements in array.

    static int findSum(int arr[], int n)

    {

        // Sum all array elements

        int sum = 0;

        for (int i = 0; i < n; i++)

            sum += arr[i];

  

        // Result is sum * 2^(n-1)

        return sum * (1 << (n - 1));

    }