We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Subset Component
  5. Discussions

Subset Component

Sort by

recency

|

69 Discussions

|

  • ayushmi274
     + 0 comments

    The quality of the problems is good, but the platform's UI and the phrasing of the problems are quite irritating.

  • patrickrfeng
     + 0 comments

    I think the example is wrong; it is missing the empty set. The test cases expect you to add the case of the empty set, but it is not present in the example.

  • adam_b_florence
     + 0 comments

    All of my tests pass except test case 0:

    def findConnectedComponents(d):
    sols = 0
    for bit in range(64):
        n_unset = sum(i & (1 << bit) == 0 for i in d)
        sols += 2 ** n_unset
    return sols + 2 ** len(d) - 1

    I count all the subsets in which each particular bit will be unset, thus solitary. Then

    add 1 for all subset, except the empty set, to count the cnon solitary components

  • khiemnd9112
     + 0 comments

    Java8 - using bitwise operations

    public static int findConnectedComponents(List<Long> d) {

    TreeMap<Long, Integer> bitsMap = new TreeMap<>();
    
    int n = d.size();
    int numOfSubsets = 1 << n;
    int res = 0;
    
    for (int i = 0; i < numOfSubsets; i ++) {
        List<Long> subset = new ArrayList<>();
                
        for (int j = 0; j < n; j++) {
            
            int mask = 1 << j;
            if ((i & mask) != 0) { 
                long cur = d.get(j);
                ListIterator<Long> iter = subset.listIterator();
                
                while (iter.hasNext()) {
                    
                    long iterCur = iter.next();
                
//iterate current subset and merge all intersected pairs
//this way there will not be any stragglers left behind
//even if met with similar cases such as {3, 12, 6} subset:
//0011
//1100
//0110
                    
                    if ((iterCur & cur) != 0) {
                        cur |= iterCur;
                        iter.remove();            
                    }
                }
                subset.add(cur);
                        
                if (bitsMap.get(cur) == null) {
                    bitsMap.put(cur, countBits(cur));
                }              
            }
        }

//as we have merged all intersected pairs, 
//the rest are naturally independent components
            
        int components = subset.size();
        
        long subsetRep = 0;
        for (Long l : subset) {
            subsetRep |= l;
        }
        
        Integer countBit = bitsMap.get(subsetRep);
        if (countBit == null) {
            countBit = countBits(subsetRep);
        }
        res += 64 - countBit + components;    
    }
    
    return res;   
}

  • yashparihar729
     + 0 comments

    Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Subset Component Problem Solution