HackerRank Subset Component Problem Solution
In this post, we will solve HackerRank Subset Component Problem Solution.
You are given an array with n 64-bit integers: d[0], d[1],…, d[n — 1].
BIT(x, i) = (x >> i) & 1, where B(x, i) is the ¿th lower bit of a in binary form. If we regard every bit as a vertex of a graph G, there is an undirected edge between vertices & and jif there is a value k such that BIT(d[k], i) == 1 && BIT(d[k], j) == 1.
For every subset of the input array, how many connected-components are there in that graph?
A connected component in a graph is a set of nodes which are accessible to each other via a path of edges. There may be multiple connected components in a graph.
Example
d = {1, 2, 3, 5}
In the real challenge, there will be 64 nodes associated with each integer in d represented as a 64 bit binary value. For clarity, only 4 bits will be shown in the example but all 64 will be considered in the calculations.
Decimal Binary Edges Node ends
d[0] = 1 0001 0
d[1] = 2 0010 0
d[2] = 3 0011 1 0 and 1
d[3] = 5 0101 1 0 and 2Consider all subsets:
Edges
Subset Count Nodes Connected components
{1} 0 64
{2} 0 64
{3} 1 0-1 63
{5} 1 0-2 63
{1,2} 0 64
{1,3} 1 0-1 63
{1,5} 1 0-2 63
{2,3} 1 0-1 63
{2,5} 1 0-2 63
{3,5} 2 0-1-2 62
{1,2,3} 1 0-1 63
{1,2,5} 1 0-2 63
{1,3,5} 2 0-1-2 62
{2,3,5} 2 0-1-2 62
{1,2,3,5} 2 0-1-2 62
Sum 944The values 3 and 5 have 2 bits set, so they have 1 edge each. If a subset contains only a 3 or 5, there will be one connected component with 2 nodes, and 62 components with 1 node for a total of 63.
If both 3 and 5 are in a subset, 1 component with nodes 0, 1 and 2 is formed since node ( is one end of each edge described. The other 61 nodes are solitary, so there are 62 connected components total.
All other values have only 1 bit set, so they have no edges. They have 64 components with
1 node each.
Function Description
Complete the findConnectedComponents function in the editor below.
findConnectedComponents has the following parameters:
- int d[n]: an array of integers
Returns
- int: the sum of the number of connected components for all subsets of d.
Input Format
The first row contains the integer n, the size of d[].
The next row has n space-separated integers, d[i].
Sample Input 1
2 5 9
Array: d3
2 5 9Sample Output 1
504Explanation 1
There are 8 subset of {2, 5, 9}.
0
=> 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 00000010. 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 00000101. There is a bit at the 0th and 2nd 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 00001001. => There is a 1-bit at the 0th and 3rd 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
S64 +64 +63 +63 +63 +63 +62 +62 = 504
Subset Component C 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;
}
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 C++ Solution
#include <bits/stdc++.h>
using namespace std;
unsigned long long arr[20];
int n;
int head[64];
int size[64];
int total_size = 64;
long long ans = 0;
int find(int n)
{
if(head[n]==n)
return n;
return find(head[n]);
}
void connect(int a, int b)
{
int fa = find(a);
int fb = find(b);
if(fa==fb)
return;
if(size[fa]>size[fb])
swap(fa,fb);
size[fb] += size[fa];
head[fa] = fb;
total_size--;
}
void rec(int pos)
{
if(pos==n)
{
ans += total_size;
return;
}
rec(pos+1);
int nhead[64];
int nsize[64];
int ntotal_size = total_size;
for(int i=0; i<64; i++)
nhead[i] = head[i], nsize[i] = size[i];
int ipos = -1;
for(int i=0; i<64; i++)
if(arr[pos]&(1ull<<i))
{
ipos = i;
break;
}
for(int i=ipos+1; i<64; i++)
if(arr[pos]&(1ull<<i))
connect(i,ipos);
rec(pos+1);
for(int i =0; i<64; i++)
head[i] = nhead[i], size[i] = nsize[i];
total_size = ntotal_size;
}
int main()
{
cin >> n;
for(int i=0; i<n; i++)
cin >> arr[i];
for(int i=0; i<64; i++)
head[i] = i,size[i] = 1;
total_size = 64;
rec(0);
cout << ans << endl;
}Subset Component C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
static void Main(String[] args) {
var n = int.Parse(Console.ReadLine());
var d = Console.ReadLine().Split(new []{ ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(i => ulong.Parse(i)).ToArray();
var result = 64;
var sets = new List<ulong[]>((int)Math.Pow(2, n));
sets.Add(Enumerable.Range(0, 64).Select(i => 1UL << i).ToArray());
var newSet = new List<ulong>(64);
for (var i = 0; i < n; ++i)
{
var count = sets.Count;
for (var j = 0; j < count; ++j)
{
newSet.Clear();
var merged = d[i];
foreach (var x in sets[j])
{
if ((x & d[i]) != 0UL)
{
merged |= x;
}
else
{
newSet.Add(x);
}
}
if (merged != 0UL)
{
newSet.Add(merged);
}
result += newSet.Count;
if (i < n - 1)
{
sets.Add(newSet.ToArray());
}
}
}
Console.WriteLine(result);
}
}Subset Component Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
private static int findConnectedComponents(long[] nums) {
Result result = new Result();
int n = nums.length;
UF[] mem = new UF[0x000F_FFFF + 1];
mem[0] = new UF(64);
generateAndAdd(0, n, nums, 0, mem, result);
return result.sum;
}
private static void generateAndAdd(int i, int n, long[] nums,
int indices, UF[] mem, Result result) {
if (i == n) {
if (indices == 0) {
result.sum += mem[0].components;
return;
}
int index = 19;
while (index >= 0 && ((1 << index) & indices) == 0) {
index--;
}
mem[indices] = new UF(mem[indices & ~(1 << index)]);
for (int l = 0; l < 63; l++) {
if ((nums[index] & (1l << l)) == 0) {
continue;
}
for (int h = l + 1; h < 64; h++) {
if ((nums[index] & (1l << h)) > 0) {
mem[indices].union(l, h);
}
}
}
//System.out.println("sum = " + mem[indices].components);
result.sum += mem[indices].components;
return;
}
// no add
generateAndAdd(i + 1, n, nums, indices, mem, result);
// with add
indices |= (1 << i);
generateAndAdd(i + 1, n, nums, indices, mem, result);
indices &= ~(1 << i);
}
private static class Result {
private int sum = 0;
}
private static class UF {
int[] uf;
int[] size;
int n;
int components;
private UF(int n) {
this.n = n;
uf = new int[n];
size = new int[n];
components = n;
for (int i = 0; i < n; i++) {
uf[i] = i;
size[i] = 1;
}
}
private UF(UF other) {
this.n = other.n;
uf = new int[this.n];
size = new int[this.n];
components = other.components;
for (int i = 0; i < this.n; i++) {
uf[i] = other.uf[i];
size[i] = other.size[i];
}
}
private boolean union(int i, int j) {
int iRoot = root(i);
int jRoot = root(j);
if (iRoot == jRoot) {
return false;
}
components--;
if (size[iRoot] <= size[jRoot]) {
uf[iRoot] = jRoot;
size[jRoot] += size[iRoot];
} else {
uf[jRoot] = iRoot;
size[iRoot] += size[jRoot];
}
return true;
}
private int root(int i) {
while (uf[i] != i) {
i = uf[i];
}
return i;
}
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int dCount = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
long[] d = new long[dCount];
String[] dItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int i = 0; i < dCount; i++) {
long dItem = Long.parseLong(dItems[i]);
d[i] = dItem;
}
int components = findConnectedComponents(d);
bufferedWriter.write(String.valueOf(components));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}Subset Component JavaScript Solution
var BigNumberConstructor = require("bignumber.js");
const cache = {};
const createGraphRepresentation = (src) => {
var id = src;
if (!cache[id]) {
var num = new BigNumberConstructor(src);
cache[id] = new GraphRepresentation(num);
}
return cache[id];
};
class GraphRepresentation {
constructor(number) {
this.bignumber = number;
this.id = number.toString();
}
get binary() {
if (!this.binaryData) {
this.binaryData = new Uint8Array(this.bignumber.toString(2).split("").map(Number));
}
return this.binaryData;
}
get verticesNum() {
if (!this.verticesData) {
var counter = 0;
for (let c of this.binary) {
if (c === 1) {
counter++;
}
}
this.verticesData = counter;
}
return this.verticesData;
}
intersects(other) {
if (!this.intersectsCache) {
this.intersectsCache = new Map();
}
var cached = this.intersectsCache.get(other);
if (cached) {
return cached;
}
var thisBinary = this.binary;
var otherBinary = other.binary;
var l = Math.min(thisBinary.length, otherBinary.length);
var retval = false;
for (var i = 1; i <= l; i++) {
if (thisBinary[thisBinary.length - i] === 1 && otherBinary[otherBinary.length - i] === 1) {
retval = true;
break;
}
}
this.intersectsCache.set(other, retval);
if (!other.intersectsCache) {
other.intersectsCache = new Map();
}
other.intersectsCache.set(this, retval);
return retval;
}
union(other) {
var thisBinary = this.binary;
var otherBinary = other.binary;
if (!this.unionCache) {
this.unionCache = new Map();
}
const cached = this.unionCache.get(other);
if (!cached) {
var l = Math.max(thisBinary.length, otherBinary.length);
var res = [];
for (var i = 1; i <= l; i++) {
var a = i > thisBinary.length ? 0 : thisBinary[thisBinary.length - i];
var b = i > otherBinary.length ? 0 : otherBinary[otherBinary.length - i];
if (a === 1 || b === 1) {
res[l - i] = 1;
}
else {
res[l - i] = 0;
}
}
var retval = createGraphRepresentation(new BigNumberConstructor(res.join(""), 2).toString());
this.unionCache.set(other, retval);
if (!other.unionCache) {
other.unionCache = new Map();
}
other.unionCache.set(this, retval);
return retval;
}
return cached;
}
equal(other) {
return this.bignumber === other.bignumber;
}
}
const getVerticesNum = (d) => {
return d.toString(2).split("1").length - 1;
};
const intersectsWithNone = new Map();
const processData = (input) => {
var reps = input.split(" ").map((a) => {
return createGraphRepresentation(a);
});
loop: for (let r1 of reps) {
let intersectsCount = 0;
for (let r2 of reps) {
if (r1.intersects(r2)) {
intersectsCount++;
if (intersectsCount > 1) {
continue loop;
}
}
}
intersectsWithNone.set(r1, true);
}
const subsets = getSubstets(reps);
var res = 0;
for (let subset of subsets) {
//console.log(subset[0]);
var subsetRes = 64;
for (let d of subset) {
//console.log("look at ", d);
subsetRes -= Math.max(0, d.verticesNum - 1);
}
//console.log(subsetRes);
res += subsetRes;
}
return res;
};
const getCombinations = (arr, value) => {
var a = [];
loop: for (var k = 0; k < arr.length; k++) {
if (((value >> k) & 1) > 0) {
var idx = k;
if (!intersectsWithNone.has(arr[idx])) {
for (var i = 0; i < a.length; i++) {
if (a[i].intersects(arr[idx])) {
a[i] = a[i].union(arr[idx]);
continue loop;
}
}
}
a.push(arr[idx]);
}
}
return a;
};
const getSubstets = (arr) => {
var l = Math.pow(2, arr.length);
var res = [];
for (var i = 0; i < l; i++) {
res.push(getCombinations(arr, i));
}
return res;
};
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
console.log(processData(_input.split("\n")[1]));
});Subset Component Python Solution
import os
import sys
def bit(x, i):
return ( x>> i) & 1
def power2(x):
return x&x-1==0
def intersect(x,y):
return x&y!=0
def combine(x,y):
return x|y
def count_cc_nodes(cc):
counter = 0
bit_length = cc.bit_length()
for i in range(bit_length):
if bit(cc,i)==1:
counter+=1
return counter
def get_connected_component_ints(new_edge_int, base_edge_ints):
# check if the new elm is a new connected component
# if it's not then return base
# if it is then continue
# compare (intersect) the new elm to each base elm
# if intersection then combine the new elm with that base elm
# then continue the comparison to each subsequent base elm using this combined
# elm as our new elm
base_edge_ints = base_edge_ints[:]
new_edge_ints = []
if power2(new_edge_int):
return base_edge_ints
else:
while base_edge_ints:
base_edge_int = base_edge_ints.pop()
if intersect(new_edge_int, base_edge_int):
new_edge_int = combine(new_edge_int, base_edge_int)
else:
new_edge_ints.append(base_edge_int)
new_edge_ints.append(new_edge_int)
return new_edge_ints
def findConnectedComponents(d):
combination_edges = dict()
c = [()]
n = len(d)
combination_edges[c[0]] = []
for i in range(n):
for j in range(len(c)):
base = c[j]
new_elm = d[i]
new_elm_key = (new_elm,)
new_combination = base + new_elm_key
#print('base:',base, 'new_elm_key:',new_elm_key,'new_combination:',new_combination)
base_edges = combination_edges[base]
new_edges = get_connected_component_ints(new_elm, base_edges)
#print('new_edges:',new_edges,'new_elm:',new_elm,'base_edges:',base_edges)
combination_edges[new_combination] = new_edges
c.append(new_combination)
#print()
#c.sort(key=lambda x: len(x))
#print(c)
#print(combination_edges)
cc_count = 0
for key in combination_edges:
connected_components = combination_edges[key]
num_cc = len(connected_components)
free_nodes = 64
for cc in connected_components:
free_nodes -= count_cc_nodes(cc)
num_cc = free_nodes + num_cc
cc_count += num_cc
#print('key',key,'num_cc',num_cc)
#print('cc_count',)
return cc_count
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
d_count = int(input())
d = list(map(int, input().rstrip().split()))
components = findConnectedComponents(d)
print(components)
fptr.write(str(components) + '\n')
fptr.close()
