This solution uses queue and deque. The primary concept is that starting from the last '1', we take all the '0's that are in between the previous '1' and the present '1'. If the previous digit is '1', then we take the last '0' that is available. If we have no '0's left, we take the first '1' that is available to us. To implement this process, we can store the indices of '0's in a queue and the indices of '1's in a deque. The time complexity is O(n).↵
↵
Code(C++): ↵
↵
~~~~~↵
//All include & defs start↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define pb push_back↵
#define dd double↵
#define ff float↵
#define ss string↵
#define ins insert↵
#define vv vector↵
↵
//All include and defs end↵
↵
//Function to solve problem starts↵
ll solve(ss s, ll n){↵
queue<ll> q;↵
deque<ll> dq;↵
for(ll i = n - 1; i >= 0; i --){↵
if(s[i] == '0'){↵
q.push(i);↵
}↵
else{↵
dq.pb(i);↵
}↵
}↵
ll ans = 0;↵
for(ll i = n - 1; i >= 0; i --){↵
if(s[i] == '1'){↵
if(! dq.empty())↵
dq.pop_front();↵
if(! q.empty()){↵
ans += (i + 1);↵
q.pop();↵
while(q.front() > dq.front() && ! q.empty()){↵
q.pop();↵
}↵
}↵
else{↵
if(! dq.empty()){↵
ans += (i + 1);↵
dq.pop_back();↵
}↵
}↵
}↵
}↵
ll total = (n * (n + 1)) / 2;↵
return total - ans;↵
}↵
↵
//Function to solve problem ends↵
↵
//main function starts↵
↵
int main(){↵
ll t;↵
cin >> t;↵
while(t --){↵
ll n;↵
cin >> n;↵
ss s;↵
cin >> s;↵
cout << solve(s, n) << endl;↵
}↵
return 0;↵
}↵
↵
//main function ends↵
~~~~~↵
↵
↵
↵
↵
↵
↵
↵
↵
Code(C++): ↵
↵
~~~~~↵
//All include & defs start↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define pb push_back↵
#define dd double↵
#define ff float↵
#define ss string↵
#define ins insert↵
#define vv vector↵
↵
//All include and defs end↵
↵
//Function to solve problem starts↵
ll solve(ss s, ll n){↵
queue<ll> q;↵
deque<ll> dq;↵
for(ll i = n - 1; i >= 0; i --){↵
if(s[i] == '0'){↵
q.push(i);↵
}↵
else{↵
dq.pb(i);↵
}↵
}↵
ll ans = 0;↵
for(ll i = n - 1; i >= 0; i --){↵
if(s[i] == '1'){↵
if(! dq.empty())↵
dq.pop_front();↵
if(! q.empty()){↵
ans += (i + 1);↵
q.pop();↵
while(q.front() > dq.front() && ! q.empty()){↵
q.pop();↵
}↵
}↵
else{↵
if(! dq.empty()){↵
ans += (i + 1);↵
dq.pop_back();↵
}↵
}↵
}↵
}↵
ll total = (n * (n + 1)) / 2;↵
return total - ans;↵
}↵
↵
//Function to solve problem ends↵
↵
//main function starts↵
↵
int main(){↵
ll t;↵
cin >> t;↵
while(t --){↵
ll n;↵
cin >> n;↵
ss s;↵
cin >> s;↵
cout << solve(s, n) << endl;↵
}↵
return 0;↵
}↵
↵
//main function ends↵
~~~~~↵
↵
↵
↵
↵
↵
↵
↵
