# MAX_BIN - Editorial

Author: hjindal
Tester: abhidot
Editorialist: iceknight1093

1143

Greedy

# PROBLEM:

Given a binary string S, you can perform the following operations on it:

• Change a 0 to a 1
• Insert a 0 anywhere in the string

Find the maximum possible integer that can be formed after at most K operations.

# EXPLANATION:

Let X be the decimal value of the string.
Let’s see how the given operations affect the value of X.

• Suppose we change bit i from 0 to 1. This increases the value of X by 2^i.
• Suppose we insert a 0 after bit i. This doesn’t change anything about bits 0, 1, 2, \ldots, i-1, but shifts bits i, i+1, \ldots to the left by one step, i.e, multiplies their values by 2.
So, if Y is the total value of bits \geq Y, X will increase by exactly Y.

From this, it’s easy to see that whenever we insert a 0, it’s always optimal to do so at the end of the string, since it directly multiplies the value of X by 2.

So, we only need to decide when to insert a 0 and when to change a 0 into a 1.
In fact, this can be done greedily!

• If the leftmost character of S is 1, then insert a 0 at the end of S
• Otherwise, change the leftmost character of S to 1.

Each operation is easily performed in \mathcal{O}(1), so the final string can be found in \mathcal{O}(N+K).

# TIME COMPLEXITY

\mathcal{O}(N + K) per test case.

# CODE:

Editorialist's code (Python)
for _ in range(int(input())):
s, k = input().split()
k = int(k)
s = list(s)
if s[0] == '0':
s[0] = '1'
k -= 1
s += ['0']*k
print(''.join(s))