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.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Subset Component
  5. Discussions

Subset Component

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 63 Discussions, By:

recency

Please Login in order to post a comment

  • mr_probable
    2 months ago+ 0 comments

    C++ Solution using bitmask and bitwise OR.

    int findConnectedComponents(vector<long> d) {
        int n = d.size();
        long long ans = 0;
        for(int i=0;i<(1<<n);++i){
            vector<long long> v;
            vector<vector<int> > a(64);
            for(long long j=0;j<n;++j){
                long long bb = pow(2, j);
                if((1<<j)&i){
                    v.push_back(d[j]);
                }
            }
            
            int par[64];
            for(int j=0;j<64;++j)par[j]=0; 
            int cnt = 0;
            set<long long> vv;
            
            for(int j=0;j<v.size();++j){
                while(1){
                    int flag = 0;
                    for(auto xx: vv){
                        if(xx&v[j]){
                            v[j]=(v[j]|xx);
                            vv.erase(xx);
                            flag=1;
                            break;
                        }
                    }
                    if(flag) continue;
                    if(flag==0)break;
                }
                vv.insert(v[j]);
            }
            cnt = 0;
            int pp = 1;
            for(auto xx: vv){
                for(int j=0;j<64;++j){
                    long long dd = pow(2, j);
                    if(xx&dd){par[j]=pp; cnt = max(cnt,pp);}
                }
                pp++;   
            }
            for(int j=0;j<64;++j)if(par[j]==0)par[j]=pp++, cnt = max(cnt, par[j]);
            vv.clear();
            ans = ans + cnt;
            v.clear();
            a.clear();
            
        }
        return ans;
    }
    
    0|
    Permalink
  • cpcbordeaux
    5 months ago+ 0 comments

    python solution

    def formatbin(s): return '{:b}'.format(s)
    
    def findConnectedComponents(d):
        # Write your code here
        
        # generate power set
        i = 1 << len(d)
        count = 0
        for s in range(i):
            # get current subset of powerset using bits of s to indicate if
            # ith element of d is in the subset
            ss = [n for ind,n in enumerate(d) if (1<<ind) & s != 0]
            #print(s, 'ss', ss)
            
            verts = 0
            connectedcount = 0
            for e in ss:
                # skip if power of 2 or zero, won't contribute to connections
                if (formatbin(e).count('1') - 1 if e else 0) < 1:
                    continue
                # check if new connected component has been found
                if not verts & e:
                    #print('new connected component', formatbin(verts), formatbin(e))
                    connectedcount += 1
                # update running vertices with connections
                verts |= e
            # get vertex count that contribute to connections
            vertcount = formatbin(verts).count('1')
            
            #print('verts', formatbin(verts), 'connectedcount', connectedcount, 'vertcount', vertcount)
            
            # update count
            sscount = 64 - vertcount + connectedcount
            count += sscount
            
            #print(sscount)
        
        return count
    
    1. loop through power set
      • this can be done by looping through [0, 2^n) and using the bits of the current value to indicate which indices of the number list define the current subset
    2. loop through elements in current subset while keeping track of vertices that contribute to connections (have an edge with another vertex) and the count of connected components (with edges)
    3. the number of total components in the graph for the given subset will be: total number of possible graphs - verts in connections + connected components (with edges)

    really thought this would be way too slow until I saw that O(n^2 * 2^n) was ok

    0|
    Permalink
  • bhautik4avenger4
    9 months ago+ 0 comments

    https://zeroplusfour.com/subset-component-hackerrank-solution/

    Here's how I did in all languages Java 8 , C++ , C , Python 3, Python 2.

    0|
    Permalink
  • h3xandcoffee
    11 months ago+ 0 comments

    Just one question, how am I to pass the 2 seconds timeout with this test case?

    19

    829270261591207363 3534642629781970875 8835486438553553922 4342777343309553910 8175455604401287800 3684624972013468915 1760786080049229631 4840400888778785676 836979242943768955 8502555703627884802 2627478096988172148 6764945274388759937 5187768558707240969 3804635763412590238 4492711122353111668 6726262505913658382 2471102837585585212 6238091755913095632 1851570362368786292

    And by the way...

    19 829270261591207363 3534642629781970875 8835486438553553922 4342777343309553910 8175455604401287800 3684624972013468915 1760786080049229631 4840400888778785676 836979242943768955 8502555703627884802 2627478096988172148 6764945274388759937 5187768558707240969 3804635763412590238 4492711122353111668 6726262505913658382 2471102837585585212 6238091755913095632 1851570362368786292 total_components: 1160959

    Process returned 0 (0x0) execution time : 289.990 s Press any key to continue.

    (On my I7 gen6 machine) :)) And not the worst code also..

    0|
    Permalink
  • luceinaltis2020
    2 years ago+ 0 comments

    I think that the editorial's time complexity is not correct.

    It is O(),not O().

    Anybody who wants to see my submission, just get to my github link!

    https://github.com/luceinaltis/Algorithms/blob/master/HackerRank_Subset_Component.cpp

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy