# PROBLEM LINK:

*Author:* Dharanendra L V

*Tester:* Dharanendra L V

*Editorialist:* Dharanendra L V

# DIFFICULTY:

Easy

# PREREQUISITES:

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.