CODEWITHSUNDEEP
java
Utkarsh
Utkarsh

Reputation: 644

How to find sum of the elements in the Subsets

I want to find the number of subsets whose elements are divisible by 2 or whose sum of the elements is divisible by 2

I have found all the possible subset of the given array

for(int i=1;i<=(Math.pow(2,n));i++) //Loop for all 2^n combinations
    {
    for(int j=0;j<n;j++)
        {
            if((i&(1<<j))>0) //This gives the subset of the array

Input:1 2 3 Output: 3 as {2},{1,3=4},{1,2,3=6} are the subsets which are divisible by 2 or whose sum of the elements is divisible by 2.

Upvotes: 0

Views: 84

Answers (1)

xerx593
xerx593

Reputation: 13299

Under the assumptions, that:

  • input is n (a natural number)
  • output is the count of "even subsets" (in a sequence of natural numbers of size n)

...the (exact) result is:

sum(binomial(n - 1, k), k in [1 .. n - 1])

respectively (=):

floor(sum(binomial(n, k), k in [1 .. n])/2)

respectively (=):

(2^(n-1)) -1

An O(log(n)) algorithm:

public class Test {


    public static long countSuperClever(int n) {
        return pow(2L, (long) n - 1) - 1L;
    }

    // best thx to https://codingforspeed.com/using-faster-integer-power-in-java/
    private static long pow(long a, long b) {
        long re = 1L;
        while (b > 0) {
            if ((b & 1) == 1) {
                re *= a;
            }
            b >>= 1;
            a *= a;
        }
        return re;
    }

    public static void main(String[] args) {
        for (int i = 3; i < 12; i++) {
            System.out.println(countSuperClever(i));
        }
    }

}

See also: https://math.stackexchange.com/a/1338830/20447

Upvotes: 1

Related Questions