My issue
on the input 0011, the expected output is 5 but it should be 4, that’s why wrong answer is coming.Anyone else facing the same issue?
My code
#include <bits/stdc++.h>
using namespace std;
vector<int> bt;
int bitSum(int i,vector<int> &bt)
{
int sum = 0;
for (i = i + 1; i > 0; i -= i & (-i))
sum += bt[i];
return sum;
}
void bitUpdate(int i, int val,vector<int> &bt)
{
for (i = i + 1; i <= 400000; i += i & (-i))
bt[i] += val;
}
int subarraysWithMoreZerosThanOnes(vector<int>& nums,vector<int> &bt) {
int res = 0, bal = 0;
bitUpdate(200000, 1,bt);
for (int num : nums) {
bal += num ? 1 : -1;
bitUpdate(bal + 200000, 1,bt);
res = (res + bitSum(bal + 200000 - 1,bt)) % 1000000007;
}
return res;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector<int> bt(400001,0);
vector<int> input;
for(int i=0;i<n;i++)
{
int element;
cin>>element;
input.push_back(element);
}
cout<<subarraysWithMoreZerosThanOnes(input,bt)<<endl;
}
}
Problem Link: Count Winning Subarrays Practice Coding Problem