 # ICCT20WC - Editorial

Author: Dharanendra L V
Tester: Dharanendra L V
Editorialist: Dharanendra L V

Easy

None.

# PROBLEM:

Given two integers N, K and a binary string S, for each character having 0 at index i, find the nearest index j having character 1 and find the sum |i - j| + k for all the valid i.

# EXPLANATION:

For each i, find the nearest 1 to its left or if not found then assign the value INT_MAX, let’s denote it as L(i) and find the nearest 1 to its right, let’s denote it as R(i) or if not found then assign the value INT_MAX. Let’s denote the final answer as ans then find the minimum of L(i) and R(i) and add it to ans and add K for every i. And at last print the value of ans. Which can be done in O(N) i.e. Linear pass.

# SOLUTIONS:

Setter's Solution
``````#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main() {

int t;
cin >> t;

while(t--) {

int n, k;
cin >> n >> k;

string s;
cin >> s;

vector<int> Left(n), Right(n);
int cnt = 0;
bool hasOne = false;
for (int i = 0; i < n; ++i)
{
if (s[i]=='1')
{
hasOne = true;
cnt = 0;
Left[i] = 0;
}
else if (hasOne)
{
cnt++;
Left[i] = cnt;
}
else
Left[i] = INT_MAX;

}

hasOne = false;
for (int i = n-1; i >= 0; --i)
{
if (s[i]=='1')
{
hasOne = true;
cnt = 0;
Right[i] = 0;
}
else if (hasOne)
{
cnt++;
Right[i] = cnt;
}
else
Right[i] = INT_MAX;
}

int sum = 0;
for (int i = 0; i < n; ++i)
{
if (s[i] != '1')
{
sum += min(Left[i], Right[i]);
}
sum += k;
}

cout << sum << endl;
}

return 0;
}

``````

Feel free to share your approach here. Suggestions are always welcomed. 1 Like