PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: maximus11
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You have two binary strings A and B of length N.
From index i, you can select either A_i or B_i, but not both.
Is it possible to make the sum of all the chosen numbers odd?
EXPLANATION:
Suppose there exists an index i such that A_i \neq B_i, i.e., either A_i = 0 and B_i = 1, or vice versa.
Then, note that it’s always possible to make the sum odd: no matter what you choose from the other N-1 indices, you can choose either 0 (if the sum is odd) or 1 (if the sum is even) from this one.
So, as long as such an index i exists, the answer is always Yes.
Otherwise, all indices of A and B have equal elements, meaning A = B.
But this means you only have a single choice at each index, so simply make that choice and check if the result is odd.
A simple way to do this is to note that you can just choose A_i always, so just check if the sum of A is odd.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = input().strip
b = input()
diff = sum(a[i] != b[i] for i in range(n))
s = sum(int(a[i]) for i in range(n))
if diff > 0 or s%2 == 1: print('Yes')
else: print('No')