Xor 4 One test case if failing

#1

Mike has got an array A of n numbers where binary representations of two consecutive numbers differ by only one bit. Now, he has a problem for you. He wants you to tell if there exists four numbers A[i1],A[ i2], A[i3],A[ i4] such that xor of these numbers is equal to 0. You can find this problem here.

Input Format
First line contains one integer n. Second line contains n space separated non-negative integers denoting the sequence A.

Constraints
4 <= n <= 100000

Output Format
Output YES if there exist four distinct indices i1, i2, i3, i4 such that A[i1] xor A[i2] xor A[i3] xor A[i4] = 0. Otherwise, output NO.

Sample Input
5
1 0 2 3 7
Sample Output
YES

MyCode:

#include
#include<bits/stdc++.h>
#define l long long int
using namespace std;

int main(){
l n;
cin>>n;
l a[n];
for(l i=0;i<n;i++){
cin>>a[i];
}
if(n > 130){
cout<<“YES”;
}
for(l i=0;i<=n-4;i++){
for(l j=i+1;j<=n-3;j++){
for(l k=j+1;k<=n-3;k++){
for(l m=k+1;m<=n-1;m++){
if(a[i]^a[j]^a[k]^a[m] == 0){
cout<<“YES”;
return 0;
}
}
}
}
}
cout<<“NO”;
return 0;
}

#2

Hi @amangoel987357

The approach you are using is wrong. How did you get to the conclusion that answer is yes if n>130.
Using new approach, as the consecutive number differ by only 1 bit, hence take a window of all 4 elements and move it across the array, and if for those for element answer comes out to be 0, then print yes else no.

Code : #include<bits/stdc++.h>
using namespace std;
#define int long long int
signed main()
{
int n;
cin >> n;
int a[n];
for(int i = 0 ; i < n; i++)
cin >> a[i];
int dp[32] = {0};
for(int i = 0 ; i+3<n;i++)
{
if(a[i]^a[i+1]^a[i+2]^a[i+3])
{
}
else
{
cout << “YES\n”;
return 0;
}
}
cout << “NO\n”;
return 0;
}

Hope it Helps.

#3

The approach which I have used is given in hint section. Now please let me know what is the mistake in my code. I am using the pigeon hole principle. Read the question once it is not mentioned anywhere that number should be consecutive. Ple

#4

Can you provide the screenshot of the hint. I do not have access to that.

I have already read the question. I said that it is given in the question that the consecutive numbers given in the array differ by only 1 bit, hence the approach. I cannot provide the proof here. Try to work it our by taking examples or mathematical, your choice.

#5

Just debug my code or else transfer this question to some other TA

#6

Ask Your Employer for screenshot