Maximum Ones
Source: codechef
Difficulty: 943

Maximum Ones
You are given a binary string$S$of length$N$consisting only of characters$0$and$1$. You are allowed to perform at most$K$operations on this string. In each operation, you can choose an index$i$(where$0 \le i < N-1$) and update the character at position$i$as follows:$S_i = \max(S_i, S_{i+1})$Here, the maximum is taken in the numerical sense, i.e.,$'1'$is considered greater than$'0'$. This operation essentially means that if$S_{i+1}$is$'1'$, then$S_i$becomes$'1'$regardless of its previous value.
Your task is to determine the maximum possible number of$1$s in the string after performing at most$K$such operations.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains two space-separated integers$N$and$K$.
The second line of each test case contains a binary string$S$of length$N$, consisting of the characters$0$and$1$.
Output Format
For each test case, output on a new line the maximum number of$1$s that can be achieved in the string after performing at most$K$operations.
Constraints$1 \leq T \leq 10^5$$1 \leq N \leq 10$$0 \leq K \leq N$$S_i \in \{0, 1\}$Sample 1:
Explanation:
Test Case 1:
You can apply the operation at index$i = 1$and the string changes to "111". Maximum possible ones = 3.
Test Case 2:
You can apply the operation at index$i = 1$and the string changes to "011". Maximum possible ones = 2.
Test Case 3:
You can apply the operation at index$i = 1$and the string changes to "011". The next operation will be applied at index$i = 0$and the string changes to "111". Maximum possible ones = 3.

Sample Input:
3
3 1
101
3 1
001
3 2
001

Sample Output:
3
2
3

C++ solution:
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long

int32_t main(){
    IOS
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        int cnt=0;
        int ok=0;
        for(int i=n-1;i>=0;--i){
            if(s[i]=='1'){
                ok=1;
            }else{
                if(ok){
                    cnt++;
                }
            }
        }
        int ans=0;
        for(auto c:s){
            ans+=(c=='1');
        }
        ans+=min(cnt,k);
        cout<<ans<<'\n';
    }
    return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func maxOnesAfterOperations(N, K int, S string) int {
    s := []rune(S) // Convert string to slice of runes for mutability

    for op := 0; op < K; op++ {
        for i := 0; i < N-1; i++ {
            if s[i] == '0' && s[i+1] == '1' {
                s[i] = '1'
                break // Perform one operation and break
            }
        }
    }

    // Count total '1's in the final string
    count := 0
    for _, ch := range s {
        if ch == '1' {
            count++
        }
    }
    return count
}

func main() {
    reader := bufio.NewReader(os.Stdin)
    writer := bufio.NewWriter(os.Stdout)
    defer writer.Flush()

    // Read all input
    input, _ := reader.ReadString('\n')
    T, _ := strconv.Atoi(strings.TrimSpace(input)) // Number of test cases

    results := make([]string, T)

    for i := 0; i < T; i++ {
        // Read N, K
        input, _ = reader.ReadString('\n')
        parts := strings.Fields(input)
        N, _ := strconv.Atoi(parts[0])
        K, _ := strconv.Atoi(parts[1])

        // Read binary string S
        S, _ := reader.ReadString('\n')
        S = strings.TrimSpace(S)

        // Compute and store result
        results[i] = strconv.Itoa(maxOnesAfterOperations(N, K, S))
    }

    // Print all results efficiently
    fmt.Fprintln(writer, strings.Join(results, "\n"))
}

Java solution:
import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
    private static PrintWriter out = new PrintWriter(System.out);
    public static void main (String[] args) throws java.lang.Exception
    {
        FastScanner fs = new FastScanner();
        int t = fs.nextInt();
        for(int c = 0; c<t; ++c)
        {
            int n = fs.nextInt(), k = fs.nextInt(), zeros = 0, ones = 0;
            String s = fs.next();
            boolean isOnefound = false;
            for(int i=n - 1; i >=0; --i)
            {
                if(s.charAt(i) == '1') 
                {
                    isOnefound = true;
                    ones++;
                }
                else
                    if(isOnefound) zeros++;
            }
                
            out.println(ones + Math.min(zeros, k));
        }
        out.close();

    }
    
    static class FastScanner
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer("");

String next()
{
while(!st.hasMoreTokens())
{
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {}
}
return st.nextToken();
}

int nextInt()
{
return Integer.parseInt(next());
}

long nextLong()
{
return Long.parseLong(next());
}

}
}

JavaScript solution:
process.stdin.resume();
process.stdin.setEncoding('utf8');

let inputString = "";
process.stdin.on('data', function (input) {
    inputString += input;
});

process.stdin.on('end', function () {
    processInput(inputString.trim());
});

function maxOnesAfterOperations(N, K, S) {
    S = S.split('');

    for (let k = 0; k < K; k++) {
        for (let i = 0; i < N - 1; i++) {
            if (S[i] === '0' && S[i + 1] === '1') {
                S[i] = '1';
                break; 
            }
        }
    }

    return S.filter(char => char === '1').length;
}

function processInput(input) {
    const data = input.trim().split(/\s+/);
    const T = parseInt(data[0], 10);
    let index = 1;
    let results = [];

    for (let t = 0; t < T; t++) {
        const N = parseInt(data[index], 10);
        const K = parseInt(data[index + 1], 10);
        const S = data[index + 2];
        index += 3;
        results.push(maxOnesAfterOperations(N, K, S));
    }

    console.log(results.join('\n'));
}

Python solution:
import sys

def main():
    input = sys.stdin.read().split()
    idx = 0
    T = int(input[idx])
    idx += 1
    for _ in range(T):
        N, K = int(input[idx]), int(input[idx+1])
        idx += 2
        S = input[idx]
        idx += 1
        original_ones = S.count('1')
        if original_ones == 0:
            print(0)
            continue
        last_one = S.rfind('1')
        possible_zeros = S[:last_one].count('0')
        add = min(K, possible_zeros)
        print(original_ones + add)

if __name__ == "__main__":
    main()

Ruby solution:
def solve_max_ones
  # Read all input at once and split into lines
  input = $stdin.read.split("\n")
  idx = 0
  test_cases = input[idx].to_i
  idx += 1
  
  test_cases.times do
    # Get N and K
    n, k = input[idx].split.map(&:to_i)
    idx += 1
    
    # Get the binary string
    s = input[idx]
    idx += 1
    
    # Count initial ones
    ones = s.count('1')
    
    # If no ones, output 0 and continue
    if ones == 0
      puts 0
      next
    end
    
    # Find position of last '1'
    last_one_pos = s.rindex('1')
    
    # Count zeros before last '1'
    zeros = s[0...last_one_pos].count('0')
    
    # Calculate how many zeros we can convert
    additional_ones = [k, zeros].min
    
    # Output total ones
    puts ones + additional_ones
  end
end

solve_max_ones