# MAX1XOR - Editorial

Author: arunsharma_
Tester: abhidot
Editorialist: iceknight1093

1381

None

# PROBLEM:

Given a binary string S, consider another binary string X such that X_{i+1} = S_i \oplus X_i for each 1 \leq i \lt N.

Find the maximum number of ones such a string can have.

# EXPLANATION:

Note that one X_1 is fixed, the rest of the string is uniquely determined, since:

• X_2 = X_1 \oplus S_1
• X_3 = X_2\oplus S_2
\vdots

But X is a binary string, so there are only two choices for X_1 — it can be either 0 or 1.
Simply try both options, construct the respective strings, and see which one has the maximum number of ones.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
ct1, ct2 = 0, 0
prv = '0'
for i in range(1, n):
if s[i-1] == prv: prv = '0'
else: prv = '1'
ct1 += prv == '1'
ct2, prv = 1, '1'
for i in range(1, n):
if s[i-1] == prv: prv = '0'
else: prv = '1'
ct2 += prv == '1'
print(max(ct1, ct2))


i think i got the logic but can’t understand why it is giving tle with s1=s1+“1”; statement and not with s1+=“1”;??

a = a + b first constructs the string a + b and the assigns it to a.
a += b directly appends b to the end of a. This takes \$

If you analyze what this means for constructing a string of length N character-by character, the first method takes \mathcal{O}(N^2) time while the second takes \mathcal{O}(N) time.

thanks

thanks for this valuable info mate