If you want a successful career in the tech field, you need to have a strong knowledge of Data Structure and algorithms to help you get. We’ll solve a question frequently asked in the technical interview based on the concept of the HashSet.
There are numerous approaches to discovering what we want. The brute force method would find all possible subsets and then identify those that satisfy our criterion.
Approach 2
The technique above is equivalent to hitting your head against a wall. Therefore, I have figured out the simplest strategies that can help you get at the answer in the shortest amount of time, saving you the shame of seeming foolish.
Every time we come across an even number, we have two options.
It may decide to either join the subgroup or not.
It may decide to exclude itself from the subset.
Therefore, the only work left for us to complete is figuring out whether or not the number is unique.
Algorithm
Maintain a HashSet to hold all of the even numbers we have come across.
Next, perform a loop.
Verify that a number is even.
If the number is even, the HashSet is added.
We then determine the number of entries in the HashSet by using self-ordering, which makes sure that only unique elements enter.
This number represents the amount of distinct even numbers that exist.
The number of subgroups may then be determined using this count.
Subset count=1 and number=2
Implementation in C++
#include <iostream>
int main() {
// Given array
int givenArray[] = {4, 2, 1, 9, 2, 6, 5, 3};
//calculating the size of the array
int n = sizeof(givenArray)/sizeof(givenArray[0]);
cout << "Number of Sets are: "
<< allEvenSets(givenArray, n);
}
int allEvenSets(int givenArray[],int n)
{
unordered_set<int>store;
//loop
for(int i=0;i<n;i++)
{
if(givenArray[i]%2==0)
store.insert(givenArray[i]);
}
int p=store.size();
return (pow(2,p)-1);
}
Output
Number of Sets are: 7
Implementation in Java
public class Main
{
public static int evenSub(int givenarray[],int n)
{
HashSet<Integer>store=new HashSet<Integer>();
//loop
for(int i=0;i<givenarray.length;i++)
{
if(givenarray[i]%2==0)
store.add(givenarray[i]);
}
// Calculating power by inbuilt function pow
int powerr=store.size();
return (int)(Math.pow(2,powerr)-1);
}
public static void main(String[] args)
{
//given array
int givenarray[] = {2, 1, 9, 2, 6, 5, 3};
//calculating length
int n = givenarray.length;
System.out.println("Number of Sets are:"+ evenSub(givenarray, n));
}
}
Output
Number of Sets are: 3
Time Complexity
O(N) Where, ‘N’ stands for the length of the array.
Reason: As we traverse the array, it is O(n). Before including an element in the subset, we evaluate each one. So the time complexity will be O(N)
Auxiliary Space Complexity
O(N), Where ‘N’ stands for the array's length.
Reason: Because we might end up storing the full array in the worst scenario, it is O(n).
How are the subsets present in the given set counted or generated?
The straightforward approach is to create all possible subsets of a given set that are 2n, where n denotes the set's size, and count the number of subsets that contain element X.
The array's subset continuous?
A subsequence need not be contiguous. However, a subarray or substring will always be contiguous. Therefore, subsequences don't need to occupy adjacent locations inside the parent sequences. Contiguous subsequence and subarray, however, are equivalent.
What is the purpose of Kadane's algorithm?
There are numerous uses for Kadane's algorithm, some of which are listed below: calculating the largest subarray sum for the given integer array. used as an algorithm for image processing. Problems like "Station Travel in Order" and "Hotels Along the Coast" can be solved using it.
Can a Subarray sum be achieved?
The aim is to determine the sum of each distinct sub-array sum. The sub-array sum is the total of all components in a specific sub-array. Note that no other sub-array will have the same sum value as the unique sub-array sum.
What does an array subsequence mean?
An ordered subset of an array's items with the same sequential ordering as the main array is referred to as a subsequence.
Conclusion
This article has gone through problems related to the subset and array.
If you identify any errors or would like to add more information to the discussion above, kindly comment.
Check out our articles in Library. You may also CheckOut our course on the array.
117+ registered 