C++ program to check xor game results 0 or not

Suppose we have an array A with N elements and another binary string S. Consider two players are playing a game. They are numbered as 0 and 1. There is one variable x whose initial value is 0. The games has N rounds. In ith round person S[i] does one of the following: replace x with x XOR A[i], otherwise do nothing. Person 0 wants 0 at the end of this game but person 1 wants non-zero. We have to check whether x becomes 0 at the end or not.

So, if the input is like A = [1, 2]; S = "10", then the output will be 1, because person1 changes x with 0 XOR 1 = 1, so it will always be 1 regardless the choice by person0.

Steps

To solve this, we will follow these steps −

N := size of A Define an array judge of size: 60. z := 0 fill judge with 0 for initialize n := N - 1, when 0 <= n, update (decrease n by 1), do:    x := A[n]    loop through the following unconditionally, do:       if x is same as 0, then:          Come out from the loop       y := x       I := -1       for initialize i := 0, when i < 60, update (increase i by 1), do:          if y mod 2 is same as 1, then:             I := i          y := y / 2       if judge[I] is same as 0, then:          judge[I] := x          Come out from the loop       x := x XOR judge[I]    if S[n] is not equal to '0', then:       if x is not equal to 0, then:          z := 1 return z

Example

Let us see the following implementation to get better understanding −

#include <bits/stdc++.h> using namespace std; int solve(vector<int> A, string S){    int N = A.size();    int judge[60];    int z = 0;    fill(judge, judge + 60, 0);    for (int n = N - 1; 0 <= n; n--){       int x = A[n];       while (1){          if (x == 0)             break;          int y = x;          int I = -1;          for (int i = 0; i < 60; i++){             if (y % 2 == 1)                I = i;                y /= 2;          }          if (judge[I] == 0){             judge[I] = x;             break;          }          x ^= judge[I];       }       if (S[n] != '0'){          if (x != 0)             z = 1;       }    }    return z; } int main(){    vector<int> A = { 1, 2 };    string S = "10";    cout << solve(A, S) << endl; }

Input

{ 1, 2 }, "10"

Output

1