A Chocolate Fiesta | HackerRank

Problem

Welcome to the exciting class of Professor Manasa. In each lecture she used to play some game while teaching a new concept. Today’s topic is Set Theory. For today’s game, she had given a set A = {a₁, a₂, …a_N} of N integers to her students and asked them to play the game as follows.

At each step of the game she calls a random student and asks him/her to select a non-empty subset from set A such that this subset had not been selected earlier and the sum of subset should be even. This game ends when all possible subsets had been selected. Manasa needs your help in counting the total number of times students can be called assuming each student gives the right answer. While it is given that if two numbers are same in the given set, they have different colors. It means that if a1 = a2, then choosing a1 and choosing a2 will be considered as different sets.

Input Format
The first line contains an integer N i.e. size of set A.
Next line will contain N integers, each representing an element of A.

Output Format
Print number of time students are called. As this number can be very large you have to print the answer modulo (10⁹ + 7).

Constraints
1 ≤ N ≤ 10⁵
0 ≤ a_i ≤ 10⁴ , where i ∈ [1 .. N]

HackerRank Problem Link

Sample Input 00

4
2 4 6 1

Sample Output 00

7

Sample Input 01

3
1 2 2

Sample Output 01

3

Explanation
There are 7 different ways in which a non-empty subset, with even sum, can be selected, i.e., {2}, {4}, {6}, {2, 4}, {2, 6}, {4, 6}, {2, 4, 6}.

For second sample test case, there are 3 different ways in which a non-empty subset, with even sum, can be selected, i.e., {a₂}, {a₃}, {a₂, a₃} which is equivalent to {2}, {2}, {2,2}.

Solution

Even sum from even numbers

We know that number of non empty subsets from a set of k numbers is

ans_even = 2^k – 1

So the number of subsets such that sum of elements is even is 2^k – 1

where k = number of even numbers.

Even sum from odd numbers

The possible ways of choosing odd number such that sum is even is by choosing even number of odd numbers . Number of possible ways using combinatorics:

^{n}{C}_2 + ^{n}{C}_4 + … + ^{n}{C}_n

Here n = number of odd numbers,

The possible number of subsets will be
ans_odd = 2^k-1 – 1

where k = number of odd numbers

Total number of subsets such that the sum is even:

ans = ans_odd + ans_even + (ans_odd*ans_even)

Note: The reason for including (ans_odd*ans_even) is that we could get an even sum if we select a set of even numbers of odd numbers and a set of even numbers.

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define mod 1000000007
using namespace std;

int temp;

int main() {
  unsigned long long ansev,ansod,ans;
  long int n,noe,noo,i;

  ansev = 1;
  ansod = 1;
  ans = 0
  noe = noo = 0;
  scanf("%ld",&n);

  for(i=0;i<n;i++) {
    scanf("%d",&temp);
    if(temp&1)
      noo++;
    else
      noe++;
  }   

  for(i=1;i<=noe;i++) {
    ansev = (long long)fmodl((ansev*2),mod);
  }

  ansev = ansev-1; 

  for(i=1;i<noo;i++) {
    ansod = (long long)fmodl((ansod*2),mod);
  }

  ansod = ansod-1;

  ans = (long long)fmodl((ansod*ansev),mod);
  ans = (long long)fmodl((ans+ansod),mod);
  ans = (long long)fmodl((ans+ansev),mod); 

  printf("%llu\n",ans);

  return 0;
}