Hashing: Given an array, count all the subsets with even numbers and are distinct

Problem Statement:

You are given an array with repeated integers, you need to count all the subsets which has only even numbers and all are distinct

Example:

Input: [2, 3, 4 ,1, 6, 9]

Output:

[2], [4], [6], [2, 4], [4, 6], [2, 4, 6], [2, 6]

Solution Explanation:

The solution is very simple.

You need to count the number of distinct even numbers.

Then apply the formula 2^evenCount -1 to get the solution.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <map>
#include <cmath>
using namespace std;


int solution(vector<int>& nums) 
{
    unordered_set<int> unorderedSet;
    int even_count = 0;
        
    for (int i=0; i < nums.size(); i++)
    {
        if (nums[i] % 2 == 0)
        {
            unorderedSet.insert(nums[i]);
        }
    }
         
    even_count = unorderedSet.size();
    
    return (pow(2, even_count) - 1);
}

int main()
{
    vector<int> a = {4, 1, 2, 3, 4, 5, 6, 7, 2, 4, 5, 8, 9};
    cout << solution(a);
    return 0;     
}

Output

15