This solution uses queue and deque. The primary concept is that starting from the last '1', we take all the zeroes that are before the previous '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++): ~~~~~
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
//Function to solve problem starts ll solve(ss s, ll n){ queue q; deque 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 ~~~~~