I guess my code works in O(N) time
CODE:-
ll t;
cin>>t;
while(t–)
{
ll n, m;
string s;
cin >> n >> m >> s;
vi pre(n), suf(n+1);
pre[0] = (s[0] == '0') ? 0 : 1;
suf[n-1] = (s[n-1] == '0') ? 0 : 1;
suf[n] = 0;
for (int i = 1; i < n; ++i) {
pre[i] = pre[i-1];
if (s[i] == '1')
++pre[i];
}
for (int i = n-2; i >= 0; --i) {
suf[i] = suf[i+1];
if (s[i] == '1')
++suf[i];
}
int ones = suf[0];
int goodIndices = 0;
if (ones == 0) {
cout << n*m << endl;
continue;
}
for (int i = 0; i < n; ++i) {
if (
(pre[i] == suf[i+1] && m%2 == 1) ||
(pre[i] > 0 && suf[i+1] == 0 && m%2 == 0) ||
(pre[i] == 0 && suf[i+1] > 0 && m%2 == 0)
) {
++goodIndices;
}
}
cout << goodIndices << endl;
}
1 Like
can you explain this logic ?
if (
(pre[i] == suf[i+1] && m%2 == 1) ||
(pre[i] > 0 && suf[i+1] == 0 && m%2 == 0) ||
(pre[i] == 0 && suf[i+1] > 0 && m%2 == 0)
) {
++goodIndices;
}
1 Like
In 1st condition its checking if it there are equal number of 1s both side and the M is odd , see if you have equal 1s both side that means its a good indices why odd M so that we can have half of the repeatitions to either side and the odd one will be at mid
example :-
5 5
11011
at index 2 you satisfy given condition if i expand it
11011 11011 11011 11011 11011
|
pointed 0 is a good index
At 2 and 3 condition i am checking if all the 1s are at one side and the M is even
example :-
3 4
011
if i expand :
011 011 011 011
|
pointed 0 is a good index
3rd condition is same as 2nd its just change the side like
2 4
110
expand:
110 110 110 110
|
good index
hk2255
August 20, 2022, 2:35pm
27
Hey, can u plz tell which test case this might be failing?
#include <iostream>
using namespace std;
#include <algorithm>
#include <vector>
#include<numeric>
using ll = long long;
// complete this simulation just to understand coding
int main()
{
int t;
cin >> t;
while(t)
{
t--;
int n, m;
string s;
cin >> n >> m >> s;
int cnt1 = 0, cnt0 = 0;
for (int i = 0; i < n; i++)
{
if(s[i] == '1') cnt1++;
else cnt0++;
}
if(cnt1 * m *1LL % 2 == 1)
{
cout << "0" << endl;
continue;
}
else if(cnt1 == 0)
{
cout << cnt0 * m * 1LL << endl;
continue;
}
string odd = s;
string even = s + s;
int oddind = 0;
int evenind = 0;
int count1 = 0;
for (int i = 0; i < odd.size(); i++)
{
if(odd[i] == '1') count1++;
if(count1 == cnt1 / 2)
{
oddind++;
i++;
while (odd[i] == '0')
{
i++;
oddind++;
}
break;
}
}
count1 = 0;
for (int i = 0; i < even.size(); i++)
{
if(even[i] == '1') count1++;
if(count1 == cnt1)
{
evenind++;
i++;
while (even[i] == '0')
{
i++;
evenind++;
}
break;
}
}
if(m % 2 == 1)
{
cout << oddind << endl;
}
else
{
cout << evenind << endl;
}
}
return 0;
}