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

|

70 Discussions

|

  • zoyashah41306
     + 0 comments

    Branded notepads can be an excellent tool for organizing and noting down key details about any project, including a subset component. Whether you're analyzing the smaller parts that make up a larger system or mapping out individual elements, these notepads help you stay organized. Customizing them with your brand adds a professional touch, ensuring your message is always front and center while staying functional for your team or clients.

  • 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
     + 3 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;   
}