 EASY MEDIUM

# PREREQUISITES

Math, Big Integer, Binary Search

# PROBLEM

How many strings of length N - where each character is `0` or `1` - exist such that number of `00` substrings is equal to `11` substrings. Further, you are given a number of at most `1000` digits and you have to verify if this is the result for some `N`.

# QUICK EXPLANATION

Pre compute the result for all N until number of digits in the answer exceed 1000 digits. Given a number, we can binary search for it in the pre computed table.

# EXPLANATION

Any valid string that starts with `0` can be transformed by replacing all `0` with `1` and `1` with `0` to get another valid string. Thus, it is sufficient to calculate the number of strings for an `N` that start with `0` and multiply the result by `2` - to get the number of valid strings of length `N`.

For some `N`

• Let `V``0` denote the number of substrings `00`
• Let `V``1` denote the number of substrings `11`
• Let `X = {X``1``, X``2``... X``p``}` denote the length of runs of `0`s
• Let `Y = {Y``1``, Y``2``... Y``q``}` denote the length of runs of `1`s

So, for a string 0011100101100

• `V``0` = `3`
• `V``1` = `3`
• `X` = `{2, 2, 1, 2}`
• `Y` = `{3, 1, 2}`

Now, a string is valid if and only if
`V``0` = `V``1`

You can see that

• `V``0` = ∑i=1 to p `(X`i `- 1)`
• `V``1` = ∑i=1 to q `(Y`i `- 1)`

Since, number of `xx` substrings in a run of `x`s of length `L` is `L-1`.
Also, the above expression for `V``0`, and `V``1` can be simplified to

• `V``0` = `(`i=1 to p `X`i`)` - `|X|`
• `V``1` = `(`i=1 to p `Y`i`)` - `|Y|`

Now,
i=1 to p `X`i is simply the number of `0`s and
i=1 to q `Y`i is the number of `1`s.

Let

• `N``0` denote the number of `0`s
• `N``1` denote the number of `1`s

The necessary and sufficient condition for a string to be a valid is

`N``0` - `|X|` = `N``1` - `|Y|`

Consider strings that start with `0` and end in `1`. It is intuitive to see that in such a string
`|X|` = `|Y|` = `k`

Thus, the necessary and sufficient condition for all strings that start in `0` and end in `1` is
`N``0` = `N``1`

Since,
`N` = `N``0` + `N``1`

`N` must be even. Thus all strings that are valid, that start in `0` and end in `1` must have the same number of `0`s and `1`s - and, this is necessary and sufficient for such strings to be valid. The number of such strings is
`N-2` `C` `(N/2) - 1`
Where `N` is even.

This result is because first and last digits are fixed and we can only choose `(N/2) - 1` digits to be 0 from the remaining `N-2` digits. The rest of them are `1`.

There cannot be an even length string that starts in `0` and ends in `1` since number of `0`s should be equal to number of `1`s and odd length strings will contradict that.

Now, consider the case of strings that start in `0` and end in `0`.
We will have the following situation
`|X|` = `|Y| + 1` = `k + 1`

Hence, the necessary and sufficient condition for all strings that start in `0` and end in `0` is
`N``0` = `N``1` `+ 1`

We see that `N` must be odd. Thus all strings that are valid, that start in `0` and end in `0` must have exactly one more `0` than `1` - and , this is necessary and sufficient for such strings to be valid. The number of such strings is
`N-2` `C` `((N-1)/2)`
Where `N` is odd.

We do not consider the case of strings that start in `1` because we have already established by symmetry that all strings that start with `0` can be transformed to obtain strings that start with `1`.

Thus, we have the complete function for the number of valid strings
`f(N)` =
`2(` `N-2` `C` `(N/2) - 1` `)`, for even `N`
`2(` `N-2` `C` `((N-1)/2)` `)`, for odd `N`

`f(2)` = 2

Iteratively build the table of pre calculated `f` values from `f(3)` to `f(t)`, where `f(t)` has more than 1000 digits. `t` will be `3333`. By building iteratively it is meant that calculating `f(k)` is possible from `f(k-1)` by doing at most one multiplication and one division.

The order of building this table should be `O(D*t)`, where `D` is the number of digits of precision you store (in this case `1000`).

Now, given a number in the input, you can binary search for this number in this table.

# SETTERS SOLUTION

Can be found here

# TESTERS SOLUTION

Can be found here
The tester uses similar inferences to arrive at the formula. He then goes on and hashes the values instead of storing them and binary searching through them (and hence is a tad bit faster).

6 Likes