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.
publicstaticintfindConnectedComponents(List<Long>d){TreeMap<Long,Integer>bitsMap=newTreeMap<>();intn=d.size();intnumOfSubsets=1<<n;intres=0;for(inti=0;i<numOfSubsets;i++){List<Long>subset=newArrayList<>();for(intj=0;j<n;j++){intmask=1<<j;if((i&mask)!=0){longcur=d.get(j);ListIterator<Long>iter=subset.listIterator();while(iter.hasNext()){longiterCur=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//0110if((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 componentsintcomponents=subset.size();longsubsetRep=0;for(Longl:subset){subsetRep|=l;}IntegercountBit=bitsMap.get(subsetRep);if(countBit==null){countBit=countBits(subsetRep);}res+=64-countBit+components;}returnres;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Subset Component
You are viewing a single comment's thread. Return to all comments →
Java8 - using bitwise operations