# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* notsoloud

*mexomerf*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

None

# PROBLEM:

You are given a binary string S.

For a fixed k between 1 and N, you can do the following:

- Exactly k times, choose an index i and flip S_i between 0 and 1.

Find the number of k such that it’s possible to make S have all its characters equal.

# EXPLANATION:

Let’s try to solve the problem for a fixed k.

In fact, let’s try to solve an even more restricted version: with this fixed k, let’s try to make the string have all 0's.

Suppose S has x ones.

Then,

- We need x moves to turn every 1 into a 0.
- After that, any move we make will turn a 0 into a 1 - so we need another move to turn it back.

So, it’s possible to turn all the characters into 0 if and only if:

- k\geq x, so that we have enough moves to even affect all the ones.
- (k-x) is even, since each extra move we make requires an additional move to revert the change.

In other words, the values of k for which it’s possible to turn all the characters into 0 are exactly

Similar reasoning tells us that if there are y zeros, the k for which all the characters can be turned into 1 are

So, simply count all the values that satisfy one of the above two properties.

Make sure not to overcount: if x = 4, y = 6 then the values 6, 8, 10 will appear in both lists, but should be counted only once.

Further, since we want k \geq 1, make sure not to count k = 0 (which you might do accidentally if x = 0 or y = 0).

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
n = int(input())
s = input()
mn = min(s.count('0'), s.count('1'))
mx = n - mn
if mn > 0: ans = len(range(mn, n+1, 2))
else: ans = len(range(2, n+1, 2))
if mn%2 != mx%2: ans += len(range(mx, n+1, 2))
print(ans)
```