[Solution] Consecutive XOR solution codechef

Consecutive XOR solution codechef – Chef has two binary strings AA and BB, both having length NN. He can perform the following operation on AA any number of times (possibly zero):

  • Select any index ii (1iN1)(1≤i≤N−1) and simultaneously set Ai:=AiAi+1Ai:=Ai⊕Ai+1 and Ai+1:=AiAi+1Ai+1:=Ai⊕Ai+1. Formally, if initially Ai=xAi=x and Ai+1=yAi+1=y then set Ai:=xyAi:=x⊕y and Ai+1:=xyAi+1:=x⊕y

Table of Contents

[Solution] Consecutive XOR solution codechef

Here,  denotes the bitwise XOR operation.

Chef wants to determine if it is possible to make AA equal to BB by applying the above operation any number of times. Can you help Chef?

Input Format

  • The first line contains a single integer TT — the number of test cases. Then the test cases follow.
  • The first line of each test case contains an integer NN — the length of the binary string AA.
  • The second line of each test case contains the binary string AA of length NN.
  • The third line of each test case contains the binary string BB of length NN.

Output Format

For each test case, output YES if Chef can make string AA equal to string BB by applying the above operation any number of times. Otherwise, output NO.

You may print each character of YES and NO in uppercase or lowercase (for example, yesyEsYes will be considered identical).

[Solution] Consecutive XOR solution codechef

  • 1T1051≤T≤105
  • 2N1052≤N≤105
  • The sum of NN over all test cases does not exceed 21052⋅105

Sample Input 1 

3
2
00
10
3
010
000
4
0011
0100

[Solution] Consecutive XOR solution codechef

 

NO
YES
YES

Explanation

Test case 11: It can be proven that we can not make AA equal to BB by using the given operation.

Test case 22: We can apply the following operations: 010⎯⎯⎯⎯011⎯⎯⎯⎯000010_→011_→000.

Test case 33: We can apply the following operations: 001⎯⎯⎯⎯10111⎯⎯⎯⎯0100001_1→0111_→0100.

For Solution

Click Here

Leave a Comment