HackwithInfy 9/01/2022 question

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

@cubefreak777 @suman_18733097

Guys please look into it

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