Count Subsets Having Distinct Even Numbers

Difficulty Level Easy
Frequently asked in Cisco Expedia Myntra SAP Labs Taxi4Sure
Array Hash SubsetViews 1439

We have all struggled with the subset problem at some point or the other in an interview. The interviewers love these problems too. These problems help them examine the understanding as well as the thought process of any student. So, without any further ado let us jump straight into the problem.

Section-1

The Problem Statement

We have been provided with a combination/array of numbers. We are to enlist the number of subsets we can have that has unique even numbers.

Let us take a small example:

Input:

[1,2,5,6,3,2,1,1,8]

Possible subsets:

[2,6]

[6,8]

[2,6,8]

Note: Subsets with the same numbers will not be considered different

Let me illustrate the same by highlighting one of the possible answer subsets.

Count Subsets Having Distinct Even Numbers

Section-2

Analysis

There is a multitude of ways to find out what we want. The brute force one would be finding all the subsets possible then finding the ones that satisfy our rule.

The above method is nothing less than banging your head against a wall. Thus, to save you the embarrassment of sounding stupid I have worked out the easiest methods that can help you get to the answer in the best time possible.

We have two choices every time we encounter an even number

  • It can either choose to be in the subset
  • It can choose to remain out of the subset

Thus, the only task we have with us now is determining if the number is unique or not. (Thanks to the aforementioned rule)

Let us zero out the process:

  • Firstly, maintain a HashSet to keep a store of the even numbers we have encountered
  • Secondly, Run a loop
  • Check if a number is even
  • If the number is even we add to it the HashSet
  • The HashSet has self-ordering that ensures that we have only the unique elements getting in
  • We then find the count of elements in the HashSet
  • This count signifies the number of unique even numbers we have
  • We can use this count to then find the number of subsets
  • Number of subsets=2^count-1

The above process can be put to code as:

Java Code for Count Subsets Having Distinct Even Numbers

public class Main
{
    public static int evenSub(int arr[],int n)
    {
        HashSet<Integer>store=new HashSet<Integer>();
        for(int i=0;i<arr.length;i++)
        {
            if(arr[i]%2==0)
                store.add(arr[i]);
        }
        int p=store.size();
        return (int)(Math.pow(2,p)-1);
    }
    public static void main(String[] args)  
    { 
    int arr[] = {2, 1, 9, 2, 6, 5, 3}; 
    int n = arr.length; 
    System.out.println
        ("Number of subsets = "+ evenSub(arr, n)); 
    }
}
2, 1, 9, 2, 6, 5, 3
3

C++ Code for Count Subsets Having Distinct Even Numbers

As we switch from Java to C++ we will be using Unordered Set instead of HashSet and flick around a few parameters to suit us.

int evenSub(int arr[],int n)
{
    unordered_set<int>store; 
    for(int i=0;i<n;i++)
    {
        if(arr[i]%2==0)
            store.insert(arr[i]);
    }
    int p=store.size();
    return (pow(2,p)-1);
}
int main() 
{
    int arr[] = {
4, 2, 1, 9, 2, 6, 5, 3
7

Complexity Analysis for Count Subsets Having Distinct Even Numbers

Time Complexity=O(n)

Space Complexity=O(n)

Time Complexity

  • It is O(n) as we go through the array
  • We look into each and every element before adding it to the subset

Space Complexity

  • It is O(n) as in the worst case we might end up storing the entire array
Translate ยป