Subset Component
You are given an array with -bit integers: .
BIT(x, i) = (x >> i) & 1, where is the lower bit of in binary form. If we regard every bit as a vertex of a graph G, there is an undirected edge between vertices and if there is a value 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
In the real challenge, there will be nodes associated with each integer in represented as a bit binary value. For clarity, only bits will be shown in the example but all 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 and have bits set, so they have edge each. If a subset contains only a or , there will be one connected component with nodes, and components with node for a total of .
If both and are in a subset, component with nodes and is formed since node is one end of each edge described. The other nodes are solitary, so there are connected components total.
All other values have only bit set, so they have no edges. They have components with 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
Input Format
The first row contains the integer , the size of .
The next row has space-separated integers, .
Constraints
xxxxxxxxxx
char* readline();
char* ltrim(char*);
char* rtrim(char*);
char** split_string(char*);
int parse_int(char*);
long parse_long(char*);
/*
* Complete the 'findConnectedComponents' function below.
*
* The function is expected to return an INTEGER.
* The function accepts LONG_INTEGER_ARRAY d as parameter.
*/
int findConnectedComponents(int d_count, long* d) {
}
int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
int d_count = parse_int(ltrim(rtrim(readline())));
char** d_temp = split_string(rtrim(readline()));
long* d = malloc(d_count * sizeof(long));
for (int i = 0; i < d_count; i++) {
long d_item = parse_long(*(d_temp + i));
*(d + i) = d_item;
}
int components = findConnectedComponents(d_count, d);
fprintf(fptr, "%d\n", 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;
}
alloc_length <<= 1;
data = realloc(data, alloc_length);
if (!data) {
data = '\0';
break;
}
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
data = realloc(data, data_length);
if (!data) {
data = '\0';
}
} else {
data = realloc(data, data_length + 1);
if (!data) {
data = '\0';
} else {
data[data_length] = '\0';
}
}
return data;
}
char* ltrim(char* str) {
if (!str) {
return '\0';
}
if (!*str) {
return str;
}
while (*str != '\0' && isspace(*str)) {
str++;
}
return str;
}
char* rtrim(char* str) {
if (!str) {
return '\0';
}
if (!*str) {
return str;
}
char* end = str + strlen(str) - 1;
while (end >= str && isspace(*end)) {
end--;
}
*(end + 1) = '\0';
return str;
}
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;
}
int parse_int(char* str) {
char* endptr;
int value = strtol(str, &endptr, 10);
if (endptr == str || *endptr != '\0') {
exit(EXIT_FAILURE);
}
return value;
}
long parse_long(char* str) {
char* endptr;
long value = strtol(str, &endptr, 10);
if (endptr == str || *endptr != '\0') {
exit(EXIT_FAILURE);
}
return value;
}