U can also choose the same index twice so nC2+n=(n*(n+1))/2
integer will overflow . you have to use long datatype for answer
For the proof of this solution , you can think of it like the string remains after removing all 0’s will give the same result as was for the original string.So for the newly made string it is clear that number of sub-strings would be n*(n+1)/2
4 Likes
https://www.codechef.com/viewsolution/26129221
can someone pls let me know what mistake i am doing
1.taking input in string
2.declared long long for product
still WA
It has to be nc1 + nc2 where n = no of zeros in string, in more detail, right?
Why this gets a WA even though I took care of overflow?
#include
#include
using namespace std;
int main(){
int T;
cin>>T;
for(int t=1;t<=T;t++){
int N;
cin>>N;
char str[1];
long long int ones=0,substrings=0;
for(int i=0;i<N;i++){
cin>>str[0];
if(strcmp(str,"1")==1){
ones++;
}
}
if(ones==1){
substrings = 1;
}
else{
substrings = ones*(ones-1);
substrings = substrings/2;
substrings = substrings + ones;
}
cout<<substrings<<endl;
}
}Please provide explanation on how you came up with this formula.
Please either format your code or link to your submission - the forum software has mangled it and it won’t compile! 
#include <bits/stdc++.h>
#include
#include
using namespace std;
int main()
{
int t,i,c=0,j=0,n;
string s1,s2;
cin>>t;
while(t–){
cin>>n;
for(i=0;i<n;i++){
cin>>s1[i];
}
for(i=0;i<n;i++){
if(s1[i]==‘1’){
j=i;
while(j<n){
if(s1[j]==‘1’)
{c++; }
j++;
}
}
}
cout<<c<<"\n";
c=0;
}
}
Pls help.Why I am getting runtime ?
Please either format your code or link to your submission - the forum software has mangled it and it won’t compile!
Edit:
It’s because you’re trying to place chars at the ith index of s1 for i = 0 … n:
for(i=0;i<n;i++){
cin>>s1[i];
}
when s1 is empty.
because of this
#include <bits/stdc++.h>
#include <string>
using namespace std;
int main()
{
long int t,i,j=0,n;
long long int c=0;
string s1;
cin>>t;
while(t--){
cin>>n;
for(i=0;i<n;i++){
cin>>s1[i];
}
for(i=0;i<n;i++){
if(s1[i]=='1'){
j=i;
while(j<n){
if(s1[j]=='1')
{
c++;
}
j++;
}
}
}
cout<<c<<"\n";
c=0;
}
}
It is running but on submission it is giving runtime error.
1 Like
Pls explain.I’m not able to understand
Try reading this:
how can “long int count” instead of “int count” make wrong answer right?my submission bcame successful when i used long int count.
https://www.codechef.com/viewsolution/29154571
Where is my code is wrong i donot understand.Please Explain.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t–){
int n;
cin>>n;
string str;
cin>>str;
int count=0;
for(int i=0;i<n;i++){
if(str[i]==‘1’){
count++;
}
}
int ans=0;
if(count==1){
ans=count;
}else if(count==2){
ans=3;
}else{
ans=(count+1)*(count);
ans=ans/2;
}
// cout<<count<<endl;
cout<<ans<<endl;
}
return 0;
}
The constraint for n is 1<=n<=10^5 but we had to take long long for storing the count value of 1’s
but count value of 1’s must be less than or equal to 10^5.
Can someone explain me why???
You don’t have to, but it makes it easier to avoid overflow when computing (num1s * (num1s - 1))/2. You could also do e.g.:
#include <iostream>
using namespace std;
int main()
{
int T;
cin >> T;
for (int t = 0; t < T; t++)
{
int n;
cin >> n;
string binaryString;
cin >> binaryString;
int num1s = 0;
for (const auto bit : binaryString)
{
if (bit == '1')
num1s++;
}
cout << (static_cast<long long int>(num1s) * (num1s - 1)) / 2 << endl;
}
}
Quite often Competitive Programmers will use long long int or an equivalent instead of int for all variables as it can be less error-prone.
2 Likes