# CSUB - Editorial

Author: Lalit Kundu
Tester: Shang Jingbo and Gerald Agapov
Editorialist: Devendra Agarwal

Cakewalk

### PROBLEM:

Given a string S consisting of only 1’s and 0’s, find the number of substrings which start and end both in 1.

### Quick Explanation

You need to find number of pairs of 1.

### Explanation

Find total number of 1’s in the given string. Let suppose that the total number of 1’s in the string is n , then the answer is (n*(n+1))/2.

Reason

Let’s suppose that the n 1’s in the string occur at x1 , x2, … , xn position in the string then all substring starting from xi and ending at xj are taken, so total possible ways in taking it is (n*(n+1))/2

Pseudo Code

``````solve(string s)
int n = 0
for ( i = 0 ; i< s.size() ; i++)
if s[i] == '1'
n++
return (n*(n+1))/2
``````

Complexity:

O(N), You just need a single pass of the string.

### AUTHOR’S and TESTER’S SOLUTIONS:

4 Likes

http://www.codechef.com/viewsolution/4290532

what is the difference?

Due to range (it could cause overflow)…I guess…In highest case value will be (10^5(10^5+1))/2 check the highest value of integer in your compiler by using INT_MAX from . can a int variable hold this much of value?? try long long datatype for holding everything…

http://www.codechef.com/viewsolution/4268643

What is wrong with this one? Says wrong answer, doesn’t seem anything is wrong though. (Submitted during the competition)

Hi,
I did this problem, can anyone please tell what is with my solution as it says wrong answer.I think everything is ok with it.
#include
#include

using namespace std;

//vector v;
void solve()
{
int n, c = 0;
string s;
cin>>n;
cin>>s;
for(int i = 0; i < n; ++i)
{
if(s[i] == ‘1’)
c++;
}
long long int a = ((c*c) + c)/2;
cout<<a<<endl;
}
int main()
{
int t;
cin>>t;
while(t–)
{
solve();
}

``````return 0;
``````

}

this is the main program of my solution, I don’t think it gives wrong answer also I am using the unsigned long long data type to evaluate the answer, what’s the problem with this solution to the problem?

``````int main(){

int T;
cin >> T;

for(int i = 0 ; i < T ; ++i){

int N;
cin >> N;

cin.ignore();

string bitString;
getline(cin,bitString);

int countOnes = 0;

for(int j = 0 ; j < (int)bitString.length() ; ++j){
if(bitString[j] == '1')
++countOnes;
}

ULL product = countOnes*(countOnes + 1);
cout << product/2 << endl;
}

return 0;
}``````

Hi, my code runs for all the test cases. But the final result is WA, this is my code, any ideas?

http://www.codechef.com/viewsolution/4339360

Change int to long long

1 Like

achaitanyasai , thank you for looking into this. I did change it, this is the new solution:http://www.codechef.com/viewsolution/4339421

Still WA

@dorsatum change flag to long long… link to AC – http://www.codechef.com/viewsolution/4339523

1 Like

@shivam217, thank you!

@ankitsablok89 The problem is due to overflow . In your code countOnes in of int type , so when you mutiply countOnes*(countOnes+1) , the ans would be of int type . If countOnes = 10^5 , then overflow would occur . To solve the problem you can cast it to long long type . Here is your corrected

``````
[1].

[1]: http://www.codechef.com/viewsolution/4341226``````

Why is my code results “Time Limit Exceeded”

#include<stdio.h>
main()
{
long long int result;
long int i,t,n,count;
char s;
scanf("%ld",&t);
while(t–)
{
count=0;
scanf("%ld",&n);
s = (char
)malloc(sizeof(char)(n+1));
fflush(stdin);
gets(s);
for(i=0;i<n;i++)
if(s[i]==‘1’)
count++;
result = (count
(count-1))/2 + count;
printf("%lld\n",result);
}
return 0;
}

Why is my code results “Time Limit Exceeded”
Code is here: http://www.codechef.com/viewplaintext/4298438

Why is my code results “SIGSEGV” Code is here: http://www.codechef.com/viewsolution/4368543

nC2 = n*(n-1)/2

@miamiheat- avoid allocating large memory inside the loop … you could have made a static array of max=10^5 outside the loop… here youtry to allocate t*n times inside which is 10^5 * 10^5 … and btw, for this question, you dont have to allocate an array… you could have done input with one variable only!

1 Like

Thanks man

I am unable to understand the problem …for 10001 , 10 1000 , 100 10001 , and 1 are also the substrings …isn’t that ??