I am trying to solve this code challenge:
Given is a binary string
sconsisting of only 0s and 1s. In a single operation, any one “1” from the string can be chosen and moved to the right until it reaches the end of the string or another “1”. The cost of the operation is 1 + the number of places the one is moved. For e.g. in the string “100010”, the first one can be moved three places to the right in cost 4. Note : it is mandatory to move a “1” to the maximum possible position to the right.Given a binary string
s, find the maximum possible number of operations possible to segregate the given string.E.g. if s = “110100”, the final string should be “000111”. The optimal way to maximize the number of operations will be :
- Swap the second and third characters at a cost of 2. The string becomes “101100”
- Swap the first and second characters at a cost of 2. The string becomes “011100”
- Finally we move each one to the end i.e. moving 2 places at a cost of 3 each.
Total cost of segregation is 2 + 2 + 3 * 3 = 13
Create a function that returns a long integer that denotes the maximum possible cost for segregating the given string.
Here’s what I did in my attempt but failed to clear the majority of the test cases, including the example given above for which my code returns 8 instead of 13:
def getMaxCost(s):
n = len(s)
cost = 0
ones = []
for i in range(n):
if s[i] == "1":
ones.append(i)
total = len(ones)
for i in range(total):
target = n - (total - i)
cost += target - ones[i]
return cost
I thought I had implemented the logic correctly. Where is my mistake?
4
The code challenge says:
the cost of the operation is 1 + the number of places the one is moved
Secondly, it could be that the same “1” can be moved multiple times, which is beneficial as for every move you get this extra point, so you need an algorithm that maximises the total number of moves.
This you can achieve by always moving the leftmost “1” that can move, after which it could be possible that its left neighbor can make a move, …etc.
This can be optimised by calculating what it costs to move the first adjacent group of 1s. This composite move will “grow” that group of adjacent 1s, which might be subject of a next composite move, ..etc.
Here is a possible implementation:
def getMaxCost(s):
cost = ones = zeroes = 0
for ch in s.lstrip("0") + "1":
if ch == "1":
if zeroes:
cost += ones * (zeroes + 1)
ones += 1
zeroes = 0
else:
zeroes += 1
return cost
2