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 2

Consider 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                    944

The 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: d

3
2 5 9

Sample Output 1

Explanation 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

HackerRank Subset Component Problem Solution

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()

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python