FastPrep
Problem · String

Move Bits to Right

Learn this problem
● MediumGoogleOA
See Google hiring insights

Problem statement

An engineer is tasked with developing an integrated binary circuit that processes an input binary string ( s ). This binary string, which consists solely of 0s and 1s, needs to be rearranged so that all 1s are moved to the end of the string. For example, the string "01010" should be transformed into "00011".

To achieve this, the engineer can perform a series of operations where any "1" from the string can be moved to the right. The operation cost is defined as ( 1 + ) the number of positions the "1" is moved. For instance, in the string "100010", moving the first "1" three positions to the right costs ( 1 + 3 = 4 ). Each "1" must be moved as far to the right as possible during the operation.

Given a binary string ( s ), determine the maximum total cost of operations required to segregate the string so that all 1s are at the end.

Function

getMaxOperationCost(s: String) → int

Examples

Example 1

s = "110100"return = 13

The target string should be "000111". To maximize the number of operations, the process would be:

  1. Move the second character to the third position at a cost of 2. The string becomes "101100".
  2. Move the first character to the second position at a cost of 2. The string becomes "011100".
  3. Move each "1" two positions to the right, each at a cost of 3.

The total cost is ( 2 + 2 + 3*3 = 13 ). Therefore, the maximum number of operations required to segregate the string is 13.

Constraints

🐹

More Google problems

drafts saved locally
public int getMaxOperationCost(String s) {
  // write your code here
}
s"110100"
expected13
checking account