Table of Contents
Subset Component – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Subset Component HackerRank Solution
#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;
}
Java Subset Component HackerRank Solution
import java.io.*;
import java.math.BigInteger;
public class Solution {
static int col = 0;
static long[] a;
public static void solve(Input in, PrintWriter out) throws IOException {
int n = in.nextInt();
a = new long[n];
for (int i = 0; i < n; ++i) {
a[i] = new BigInteger(in.next()).longValue();
}
int ans = 0;
for (int mask = 0; mask < 1 << n; ++mask) {
col = 0;
int countBits = 64;
int add = 0;
for (int i = 0; i < n; ++i) {
if (((mask & ~col) & (1 << i)) != 0) {
long mask1 = dfs(i, mask);
if (mask1 != 0) {
add++;
countBits -= Long.bitCount(mask1);
}
}
}
add += countBits;
ans += add;
}
out.println(ans);
}
private static long dfs(int i, int mask) {
if ((col & (1 << i)) != 0) {
return 0;
}
col |= 1 << i;
long ret = a[i];
for (int j = 0; j < a.length; ++j) {
if ((mask & (1 << j)) != 0 && (a[i] & a[j]) != 0) {
ret |= dfs(j, mask);
}
}
return ret;
}
public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(System.out);
solve(new Input(new BufferedReader(new InputStreamReader(System.in))), out);
out.close();
}
static class Input {
BufferedReader in;
StringBuilder sb = new StringBuilder();
public Input(BufferedReader in) {
this.in = in;
}
public Input(String s) {
this.in = new BufferedReader(new StringReader(s));
}
public String next() throws IOException {
sb.setLength(0);
while (true) {
int c = in.read();
if (c == -1) {
return null;
}
if (" \n\r\t".indexOf(c) == -1) {
sb.append((char)c);
break;
}
}
while (true) {
int c = in.read();
if (c == -1 || " \n\r\t".indexOf(c) != -1) {
break;
}
sb.append((char)c);
}
return sb.toString();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
}
}
Python 3 Subset Component HackerRank Solution
from functools import reduce
from operator import or_
def get_integers():
from sys import stdin
return int(stdin.readline().strip()), sorted(map(int, stdin.readline().strip().split()))
def dec(s):
return '{:b}'.format(s).count('1')-1 if s else 0
def compute(head, *tail):
hc = dec(head)
if tail:
last, d = compute(*tail)
#print('->', last, d)
new = []
d_ = d
for k,v in last:
if all(t&head==0 for t in k):
x = v+hc
d_ += x
new.append((k+(head,), x))
else:
A = tuple(t for t in k if t&head==0)
b = reduce(or_, (t for t in k if t&head!=0), head)
#print('A', A)
#print('b', b)
x = dec(sum(A)+b)-len(A)
d_ += x
new.append((A+(b,), x))
new_ = new + last
#print('<-', new_, d_)
return new_, d_
else:
return [((),0), ((head,), hc)], hc
n, I = get_integers()
print(64*2**n - compute(*I)[1])
Python 2 Subset Component HackerRank Solution
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()
C Subset Component HackerRank Solution
#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 NULL;
}
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;
}
Leave a comment below
