 # Xor subsequences , Hacker rank Help!

Hello everyone!, I am trying to solve this problem,O(n^2) will pass with some optimization but there is one solution using a variation of FFT, please can anyone help me with this, how this solution is achieved.

solution is in editorial section on the problem page : https://www.hackerrank.com/challenges/xor-subsequence/editorial

Or find problem statement below.

Problem Statement

You are given N integers: A1, A2, A3, …, AN. We pick up a consecutive subsequence of integers from the given series. A[i], A[i+1], … A[j-1], A[j], (1 <= i <= j <= N). For example, if N = 3:
The subsequences we may consider are

A
A
A
A,A
A,A
A,A,A

For each subsequence, we apply the bitwise XOR operation to all the integers and record the value of this XOR operation. Since there are N x (N+1)/2 subsequences, we obtain N x (N + 1) / 2 numbers.

Your task is to find the most frequent number in the recorded list and how many times it appears.

Input Format

The first line contains an integer N (1 ≤ N ≤ 100000). This is followed by N lines, each containing one integer Ai per line. (1 ≤ Ai < 2^16).

Output Format

Output one line contains the most frequent number and how many times it appears. If there is multiple number that has the most frequency, choose the minimum number.

Sample Input

4
2
1
1
3

Sample output

1 3

Explanation

Finding the XOR in all the consecutive subsequences:
2 = 2
2 ^ 1 = 3
2 ^ 1 ^ 1 = 2
2 ^ 1 ^ 1 ^ 3 = 1
1 = 1
1 ^ 1 = 0
1 ^ 1 ^ 3 = 3
1 = 1
1 ^ 3 = 2
3 = 3

1, 2, 3 are all repeated three times. Since we are looking for the minimum number, 1 is the answer.

hey i am stuck at a point in c programming.
i am using turbo c as my compiler,
whenever i use float in my program ,the output i am getting is -NAN or -INF .please help me to get out of it.

There must be some logical or manipulation mistake in your code. Nan refers to Not-a-Number which comes in cases like taking square roots of -ve numbers. Print intermediate values in your code and check the output.