XOR Subsequences
Consider an array, , of integers (). We take all consecutive subsequences of integers from the array that satisfy the following:
For example, if our subsequences will be:
For each subsequence, we apply the bitwise XOR () operation on all the integers and record the resultant value. Since there are subsequences, this will result in numbers.
Given array , find the XOR sum of every subsequence of and determine the frequency at which each number occurs. Then print the number and its respective frequency as two space-separated values on a single line.
Input Format
The first line contains an integer, , denoting the size of the array.
Each line of the subsequent lines contains a single integer describing element .
Constraints
Output Format
Print space-separated integers on a single line. The first integer should be the number having the highest frequency, and the second integer should be the number's frequency (i.e., the number of times it appeared). If there are multiple numbers having maximal frequency, choose the smallest one.
Sample Input 0
4
2
1
1
3
Sample Output 0
1 3
Explanation 0
Let's find the XOR sum for all consecutive subsequences. We'll refer to the frequency of some number as , and keep a running sum for each frequency:
- , frequencies:
- , frequencies: and
- , frequencies: and
- , frequencies: , , and
- , frequencies: , , and
- , frequencies: , , , and
- , frequencies: , , , and
- , frequencies: , , , and
- , frequencies: , , , and
- , frequencies: , , , and
Our maximal frequency is , and the integers , , and all have this frequency. Because more than one integer has this frequency, we choose the smallest one, which is . We then print the respective smallest number having the maximal frequency and the maximal frequency as a single line of space-separated values.
xxxxxxxxxx
char* readline();
char* ltrim(char*);
char* rtrim(char*);
int parse_int(char*);
long parse_long(char*);
/*
* Complete the 'xorSubsequence' function below.
*
* The function is expected to return an INTEGER_ARRAY.
* The function accepts LONG_INTEGER_ARRAY a as parameter.
*/
/*
* To return the integer array from the function, you should:
* - Store the size of the array to be returned in the result_count variable
* - Allocate the array statically or dynamically
*
* For example,
* int* return_integer_array_using_static_allocation(int* result_count) {
* *result_count = 5;
*
* static int a[5] = {1, 2, 3, 4, 5};
*
* return a;
* }
*
* int* return_integer_array_using_dynamic_allocation(int* result_count) {
* *result_count = 5;
*
* int *a = malloc(5 * sizeof(int));
*
* for (int i = 0; i < 5; i++) {
* *(a + i) = i + 1;
* }
*
* return a;
* }
*
*/
int* xorSubsequence(int a_count, long* a, int* result_count) {
}
int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
int a_count = parse_int(ltrim(rtrim(readline())));
long* a = malloc(a_count * sizeof(long));
for (int i = 0; i < a_count; i++) {
long a_item = parse_long(ltrim(rtrim(readline())));
*(a + i) = a_item;
}
int result_count;
int* result = xorSubsequence(a_count, a, &result_count);
for (int i = 0; i < result_count; i++) {
fprintf(fptr, "%d", *(result + i));
if (i != result_count - 1) {
fprintf(fptr, " ");
}
}
fprintf(fptr, "\n");
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;
}
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;
}