The following questions was asked in my hackwithinfy paper.
You are given an array of N non-negative integers.
Mr. Ara wants to split array into groups such that each array meets the following conditions:
- XOR of all integers in each group is equal to 0.
. groups are non-empty and contain consecutive integers.
• each Integer of array belongs to exactly one group.
Mr. Ara also wants the number of groups to be as much as possible.
Your task is to find the maximum possible number of groups that Mr. Ara can achieve or 0 if such splitting doesn’t exit
Input Format
The first line contains an integer, N, denoting the number of elements in A.
Each line i of the N subsequent lines (where 0 << N) contains an integer describing Ai
Constraints
1 <= N <= 10^5
0 <=A[i]<= (2^30)-1
Eg:-
Sample Input
8
3
3
4
4
0
0
2
2
Sample Output
5
Explanation
The optimal splitting is [3,3][4,4][0][0][2,2]
Sample input 2
8
6
6
0
6
2
4
0
6
Output:- 0
Explanation:-
There is no valid splitting
Sample input 3:-
5
0
6
4
2
0
Output:-
3
Explanation:-
The optimal splitting is [0],[6,4,2],[0]
My approach was simple :- keep moving right as long as pairs are being formed. If any bigger value is followed by a smaller value and the bigger value
Is not in any given pair then return 0.
This approach passed all the public but 1/12 private cases were passed.
I wonder what could have been done in this one.
Please help me
This is what I understood:
We should divide arr into sub-arrays such that the EX-OR of elements of each sub-array is 0. We need to maximise the number of sub-arrays, right?
1 Like
If the XOR of all the elements in the array is 0, then and then only it is possible to split the array into groups.
Because, each element of array is present in any one group and since the XOR of each group should be 0, so the XOR of all such groups must be evaluated to 0. ( 0^0^0^…0 = 0 )
And also we have to take consecutive elements from array, so we can just iterate from the start until we get XOR as 0. That will be considered as single group and start another group from that position onwards, that will be another group.
Why this works?
Because we have already checked the XOR of all elements from array whether results in 0 or not. So there would be at-least one group (whole array) which has XOR as 0.
I don’t know whether this approach is correct or not, but it is passing those test cases described in this post.
int main()
{
int n;
cin >> n;
vector<int> ar(n);
int ans = 0;
for (int i = 0; i < n; i++)
{
cin >> ar[i];
ans ^= ar[i]; // XORing all the elements of the array
}
if (ans != 0)
{
cout << "NOT VALID SPLITTING" << endl;
return 0;
}
vector<vector<int>> arr; // array for storing all those resultant subarrays
for (int i = 0; i < n; i++)
{
if (ar[i] == 0) // if it is 0, it has already XOR as 0
{
arr.push_back({0});
continue;
}
ans = ar[i];
vector<int> temp; // array for storing the subarray
temp.push_back(ar[i]);
for (int j = i + 1; j < n; j++)
{
ans ^= ar[j];
temp.push_back(ar[j]);
if (ans == 0)
{
arr.push_back(temp);
i = j;
break;
}
}
}
cout << arr.size() << endl;
for (int i = 0; i < arr.size(); i++) // printing those subarray which has XOR 0
{
for (int j = 0; j < arr[i].size(); j++)
{
cout << arr[i][j] << " ";
}
cout << endl;
}
return 0;
}```
2 Likes
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
int cnt = 0;
int x = 0;
for(int i=0;i<n;i++){
x = x^a[i];
if(x==0){
cnt++;
}
}
if(cnt==0 || x!=0){
cout<<-1<<endl;
}
else{
cout<<cnt<<endl;
}
return 0;
}
1 Like
yup pretty much sums it up
yup, I see that your test cases are passing but the thing is my approach was similar to this yet most of the private test cases failed.
I want to know what further optimizations were being expected from these solutions?
yup same thing we traversed but this was not passing private cases
