Subset Component HackerRank Solution in C, CPP, Python

There are  subset of .

{}
=> We don’t have any number in this subset => no edge in the graph => Every node is a component by itself => Number of connected-components = 64.

{2}
=> The Binary Representation of 2 is . There is a bit at only one position. => So there is no edge in the graph, every node is a connected-component by itself => Number of connected-components = 64.

{5}
=> The Binary Representation of 5 is . There is a bit at the 0^th and 2^nd position. => So there is an edge: (0, 2) in the graph => There is one component with a pair of nodes (0,2) in the graph. Apart from that, all remaining 62 vertices are indepenent components of one node each (1,3,4,5,6…63) => Number of connected-components = 63.

{9}
=> The Binary Representation of 9 is . => There is a 1-bit at the 0^th and 3^rd position in this binary representation. => edge: (0, 3) in the graph => Number of components = 63

{2, 5}
=> This will contain the edge (0, 2) in the graph which will form one component
=> Other nodes are all independent components
=> Number of connected-component = 63

{2, 9}
=> This has edge (0,3) in the graph
=> Similar to examples above, this has 63 connected components

{5, 9}
=> This has edges (0, 2) and (0, 3) in the graph
=> Similar to examples above, this has 62 connected components

{2, 5, 9}
=> This has edges(0, 2) (0, 3) in the graph. All three vertices (0,2,3) make one component => Other 61 vertices are all independent components
=> Number of connected-components = 62

Subset Component HackerRank Solution in C

#include <stdio.h>
#include <stdlib.h>
typedef struct _list{
  unsigned long long data;
  struct _list *next;
} list;
int count_long(unsigned long long n);
int count(int i);
list *get(list **head);
void *put(list **head,list *c);
void process(unsigned long long *a,int *b,list **free_head,int n,int index,int bi,int *ans);

int main(){
  int n,ans=0,i,*b;
  unsigned long long *a;
  list *free_head;
  scanf("%d",&n);
  free_head=(list*)malloc(n*sizeof(list));
  a=(unsigned long long*)malloc(n*sizeof(unsigned long long));
  b=(int*)malloc(n*sizeof(int));
  for(i=0;i<n-1;i++)
    free_head[i].next=free_head+i+1;
  free_head[i].next=NULL;
  for(i=0;i<n;i++)
    scanf("%llu",a+i);
  process(a,b,&free_head,n,0,0,&ans);
  printf("%d",ans);
  return 0;
}
int count_long(unsigned long long n){     
  return count(n)+count(n>>32);
}
int count(int i){
  i = i - ((i >> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
  return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
list *get(list **head){
  list *c=*head;
  *head=(*head)->next;
  return c;
}
void *put(list **head,list *c){
  c->next=*head;
  *head=c;
  return;
}
void process(unsigned long long *a,int *b,list **free_head,int n,int index,int bi,int *ans){
  if(index==n){
    int i;
    unsigned long long d;
    list *head=NULL,*p,*c,*temp;
    (*ans)+=64;
    for(i=0;i<bi;i++){
      d=a[b[i]];
      c=head;
      p=NULL;
      while(c){
        if(d&c->data){
          d|=c->data;
          if(!p)
            head=c->next;
          else
            p->next=c->next;
          temp=c;
          c=c->next;
          put(free_head,temp);
          continue;
        }
        p=c;
        c=c->next;
      }
      p=get(free_head);
      p->data=d;
      p->next=head;
      head=p;
    }
    while(head){
      i=count_long(head->data);
      (*ans)-=(i)?i-1:0;
      temp=head;
      head=head->next;
      put(free_head,temp);
    }
    return;
  }
  process(a,b,free_head,n,index+1,bi,ans);
  b[bi++]=index;
  process(a,b,free_head,n,index+1,bi,ans);
  return;
}

Subset Component HackerRank Solution in CPP

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
#define FOREACH(it,arr) for (__typeof((arr).begin()) it=(arr).begin(); it!=(arr).end(); it++)

typedef unsigned long long ULL;

int n;
ULL d[30];

int p[65], r[65];
vector <int> v[30];

int find(int x) {
	if ( p[x] != x ) p[x] = find(p[x]);
	return p[x];
}
void link(int x, int y) {
	if ( r[x]  < r[y] ) r[x]++;
	if ( r[x] == r[y] ) p[x] = p[y]; else p[y] = p[x];
}


int f(int x) {
	int ret = 0;
	if ( x == n ) {
		bool flag[65] = {false};
		REP(j,64) flag[find(j)] = true;
		REP(j,64) ret += flag[j];
		return ret;
	}
	int tp[65], tr[65];

	memcpy(tp,p,sizeof(p));
	memcpy(tr,r,sizeof(r));

	ret += f(x+1);

	memcpy(p,tp,sizeof(p));
	memcpy(r,tr,sizeof(r));
	
	FOR(j,1,v[x].size()-1)
		link(find(v[x][j]),find(v[x][0]));
	
	ret += f(x+1);
	

	return ret;
}


int main()
{
	cin >> n;
	REP(i,n) cin >> d[i];

	REP(i,n) REP(j,64) if ( (d[i] >> j) & 1 ) v[i].push_back(j);

	REP(j,64) p[j] = j, r[j] = 0;
	cout << f(0) << endl;

	return 0;
}

Subset Component HackerRank Solution in Python

def find(l, i):
    if l[i]!=i: l[i] = find(l, l[i])
    return l[i]

def go():
    n = input()
    d = map(int, raw_input().split())
    l = range(n)
    for i in range(n):
        for j in range(i):
            if d[i]&d[j]:
                fi = find(l, i)
                fj = find(l, j)
                l[fi] = l[fj]
    q = [[] for i in range(n)]
    for i in range(n):
        q[find(l,i)].append(d[i])
    res = 64<<n
    for i in range(n):
        if q[i]:
            lq = len(q[i])
            v = (64<<lq) - f(lq, q[i])
            res -= (1<<(n - lq)) * v
    print res

def f(n, d):
    res = 64
    dp = [0]*(1<<n)
    dp[0] = [1<<i for i in range(64)]
    for i in range(1, 1<<n):
        for j in range(n):
            if i&(1<<j): break
        v = d[j]
        q = dp[i&(i-1)]
        if v:
            l = []
            for x in q:
                if x&v: v|=x
                else: l.append(x)
            l.append(v)
            res += len(l)
            dp[i] = l
        else:
            res += len(q)
            dp[i] = q
    return res

go()