AlgoUniversity
  • Go Back
Discussion
Shifting Homes :

Author

Lokesh

Difficulty Level : Medium

Submissions : 537

Asked In : Samsung

Marks :10

: 10 | : 0

Homes are aligned in a row. In any given row, maximum half of the homes are occupied by families. In a season,people got infected and all families must vacate homes to move to initially unoccupied homes.

Movements are sequential and not parallel (i.e one family completes the movement, then only the second family starts). To reduce the overall time taken, it's better to move to a nearby empty room than a farther one. $$$i^{th}$$$ home to $$$j^{th}$$$ home movement results in $$$|j-i|$$$ time. Minimize the overall time taken by all families to complete the movement to unoccupied homes.

Input

First line contains integer $$$1 \le N \le 10000$$$, Number of homes

Second line contains a string $$$S$$$, of length $$$N$$$, denoting occupied and unoccupied homes($$$1$$$ = occupied, $$$0$$$ = unoccupied)

Number of unoccupied homes $$$\ge$$$ Number of occupied homes

Output

Integer denoting minimum overall time taken for all families to move to unoccupied homes

Examples

Input
4
1001
Output
2
Input
8
00101101
Output
8

You need to login to view your submissions.

You need to login to view all submissions.

Loading...

Result : Executed

Loading...

Feel something is wrong with the test cases?

Result : Accepted

Test Cases :

You need to Log In
We're glad that you want to attempt this problem!

But to Run or Submit the Problem, you need to Log In.

Continue to Log In
Challenge Submitted!

Your challenge has been submitted successfully.

You will get a response soon via WhatsApp or Email.

Challenge
Facing issue while trying to solve the problem! Don't worry, we got you covered!

Do let us know your issue.

Looks good!
Please enter your issue / feedback.

How do we get in touch with you?
Looks good!
Please enter your phone no.
Looks good!
Please enter your email address.