Subset Component
Subset Component
+ 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 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
- 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
- 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)
- 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
- loop through power set
+ 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 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 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
Sort 63 Discussions, By:
Please Login in order to post a comment