 < Back to forum

### Help in understanding editorial.

Hii, I had been reading the editorial to this problem, and I find it difficult for me to understand the concept of `out` comments used here.

Asked by: mahawarvishal10 on Dec. 31, 2020, 4:27 p.m. Last updated on Dec. 31, 2020, 4:27 p.m.

Comment-1

Comment-2

Test Ignore this

Preview

##### Enter your comment details below:

Preview

Firstly the editorial asks, to select any two consecutive '?'s in a given string s , for exammple, s[L] and s[R]

Then it asks to calcuate the following two things :

1) put s[L] = 0, and s[R] = 1

`````` where c1 being --> count of  "1" in the range [ L, R ] not inclusive in s;
where c0 being --> count of  "0" in the range [ L, R ] not inclusive in s;

Now what do we observe?

-->s[L] will pair up with all the 1s in the range ( L, R ) not inclusive.
which wil be c1

-->s[L] will pair up with all the 1s from [R+1, N] inclusive
Let this be OUT1

--> s[L] will pair up with all the 1s from [1, L-1] incsulive
Let this be OUT2

-->s[R] will pair up with all the 0s in the range (L,R) not inclusive.
which will be c0

-->s[R] will pair up with all the 0s from [R+1, N] inclusive
Let this be OUT3

-->s[R] will pair up with all the 0s from [1, L-1] inclusive
Let this be OUT4

--> Add 1 as we added s[L] = 0, s[R] =1, hence "01"

so the total pairs =  c1 + c0 + 1 + OUT1 + OUT2 + OUT3 + OUT4
=  R-L  + OUT
to get the value we multiply x   = (R-L)*x + OUT  --> Equation I
``````

2) put s[L] = 1 and s[R] = 0

`````` where c1 being --> count of  "1" in the range [ L, R ] in s;
where c0 being --> count of  "0" in the range [ L, R ] in s;

now we just swapped the positions, so previous s[R] is now s[L]
hence has (R-L) new elements on the right with same old right side
elements from [R+1, N] which was OUT3

and if you notice for all possible pairs, you'll find it will from the same count
equation with the unchanged OUT

to get the value we multiply with y = (R-L)*y + OUT  --> Equation II

if we subtract 2 equations( Equation I and II) we get

(R-L) * (x-y) <-- we need to minimize this

so it solely depends on which is smaller among two of x and y:
if x is smaller we tend to keep 10 or else 01

Now with some intuition we can come to this conlusion :

we can fill the entire '?' with 1 or 0
like in ?????? = 111111 or 000000
and greedily change every prefix to other value, like if you want to establish
01 we can change the prefixes to 0s  and vice versa, and find the min of all the possibilities.
``````

This can be done in O(n)

ashnove last updated on Jan. 3, 2021, 7:52 p.m.

.

Sourav last updated on Jan. 12, 2021, 11:18 a.m.

##### Instruction to write good question
1. 1. Write a title that summarizes the specific problem
2. 2. Pretend you're talking to a busy colleague
3. 3. Spelling, grammar and punctuation are important!