HackerRank Subset Component problem solution

In this 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 ith lower bit of x in binary form. If we regard every bit as a vertex of a graph G, there is an undirected edge between vertices i and j if 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 that are accessible to each other via a path of edges. There may be multiple connected components in a graph.

Problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the findConnectedComponents function below.
def count_components(i, prev_components, cliques):
    ''' Back-tracking algorithm '''
    if i >= len(cliques):
        return len(prev_components)
    c = count_components(i+1, prev_components, cliques)
    # now add a clique
    new_comp = cliques[i]
    components = []
    for comp in prev_components:
        if comp & new_comp:
            new_comp |= comp
        else:
            components.append(comp)
    if new_comp:
        components.append(new_comp)
    c += count_components(i+1, components, cliques)
    return c

if __name__ == '__main__':
    n = int(input().strip())
    d = input().strip().split()
    d = [int(v) for v in d]
    assert len(d) == n
    
    singletons = [1<<j for j in range(64)]
    print(count_components(0, singletons, d))

Problem solution in Java.

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("(rn|[nru2028u2029u0085])?");

        long[] d = new long[dCount];

        String[] dItems = scanner.nextLine().split(" ");
        scanner.skip("(rn|[nru2028u2029u0085])?");

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

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstdint>
#include <cstring>
#include <memory>

using namespace std;

static const int BITS = 64;

class Num {
private:
    struct Component {
        int parent;
        int h;
    };
    Component cs[BITS];
    
    int getparent(int i) {
        if (i == cs[i].parent)
            return i;
        return cs[i].parent = getparent(cs[i].parent);
    }
    void join(int a, int b) {
        a = getparent(a);
        b = getparent(b);
        if (a == b)
            return;
        if (cs[a].h > cs[b].h) {
            cs[b].parent = a;
        } else if (cs[a].h < cs[b].h) {
            cs[a].parent = b;
        } else {
            cs[b].parent = a;
            ++cs[a].h;
        }
    }
public:
    Num(uint64_t x) {
        for (int i = 0; i < BITS; ++i) {
            cs[i].parent = i;
            cs[i].h = 1;
        }
        for (int i = 0; i < BITS; ++i)
            for (int j = 0; j < BITS; ++j)
                if ((x >> i) & 1 == 1 & (x >> j) & 1 == 1)
                    join(i, j);
    }
    Num& operator=(const Num& other) {
        memcpy(cs, other.cs, sizeof(cs));
        return *this;
    }
    Num (const Num &other) {
        *this = other;
    }
    int components() const {
        int result = 0;
        for (int i = 0; i < BITS; ++i)
            if (cs[i].parent == i)
                ++result;
        return result;
    }
    void sum(const Num &other) {
        for (int i = 0; i < BITS; ++i)
            join(i, other.cs[i].parent);
    }
};
template<typename T>
class Restorer {
private:
    T orig;
    T &ref;
    Restorer(const Restorer &);
    Restorer &operator=(const Restorer &);
public:
    Restorer(T &obj)
        : orig(obj)
        , ref(obj)
        { }
    void restore() {
        ref = orig;
    }
};
void backtrack(int &result, Num &state, const vector<shared_ptr<Num> > &ns, int idx) {
    if (idx == ns.size()) {
        result += state.components();
        return;
    }
    Restorer<Num> rest(state);
    backtrack(result, state, ns, idx+1);
    rest.restore();
    state.sum(*ns[idx]);
    backtrack(result, state, ns, idx+1);
    rest.restore();
}
int main() {
    int n;
    vector<shared_ptr<Num> > ns;
    for (cin >> n; n > 0; --n) {
        uint64_t x;
        cin >> x;
        ns.push_back(shared_ptr<Num>(new Num(x)));
    }
    int result = 0;
    Num empty(0);
    backtrack(result, empty, ns, 0);
    cout << result << 'n';
    return 0;
}

Problem solution in C.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 64

char* readline();
char** split_string(char*);

struct cpntlist{
    long cpnts[SIZE];
};

// Complete the findConnectedComponents function below.
int findConnectedComponents(int d_count, long* d) {
    int toreturn = SIZE;
    struct cpntlist *cpnts = malloc(sizeof(struct cpntlist)<<d_count);
    for(int i = 0; i < SIZE; i++){
        cpnts[0].cpnts[i] = ((long)1)<<i;
    }


    for(int i = 0; i < d_count; i++){
        long mask = d[i];
        for(int j = 0; j < 1<<i; j++){
            struct cpntlist oldlist = cpnts[j];
            int firstcpnt = -1;
            int next = (1<<i) + j;

            int numcpnts = 0;
            for(int k = 0; k < SIZE; k++){
                if((mask&oldlist.cpnts[k]) != 0){
                    if(firstcpnt == -1){
                        firstcpnt = k;
                        cpnts[next].cpnts[k] = oldlist.cpnts[k];
                        numcpnts++;
                    }
                    else{
                        cpnts[next].cpnts[firstcpnt] |= oldlist.cpnts[k];
                        cpnts[next].cpnts[k] = 0;
                    }
                }
                else if(oldlist.cpnts[k] != 0){
                    cpnts[next].cpnts[k] = oldlist.cpnts[k];
                    numcpnts++;
                }
                else{
                    cpnts[next].cpnts[k] = 0;
                }
            }
            toreturn += numcpnts;
        }
    }
    return toreturn;
}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char* d_count_endptr;
    char* d_count_str = readline();
    int d_count = strtol(d_count_str, &d_count_endptr, 10);

    if (d_count_endptr == d_count_str || *d_count_endptr != '') { exit(EXIT_FAILURE); }

    char** d_temp = split_string(readline());

    long* d = malloc(d_count * sizeof(long));

    for (int i = 0; i < d_count; i++) {
        char* d_item_endptr;
        char* d_item_str = *(d_temp + i);
        long d_item = strtol(d_item_str, &d_item_endptr, 10);

        if (d_item_endptr == d_item_str || *d_item_endptr != '') { exit(EXIT_FAILURE); }

        *(d + i) = d_item;
    }

    int components = findConnectedComponents(d_count, d);

    fprintf(fptr, "%dn", components);

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == 'n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == 'n') {
        data[data_length - 1] = '';
    }
    if(data[data_length - 1] != ''){
        data_length++;
        data = realloc(data, data_length);
        data[data_length - 1] = '';
    }

    data = realloc(data, data_length);

    return data;
}

char** split_string(char* str) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);
        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ");
    }

    return splits;
}