# Given a binary string find the number of substring that can formed such that every substring starts with \"1\" and ends with \"1\"

### All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

**Algorithm:**

Though it's a string problem, it can be solved actually using simple combinatorics.

- Calculate total no of '1' occurring in the string

Set count 0; (count is to store frequency of '1') For each character at index i of the string IF(string[i]=='1') Increment count; END IF END FOR

- Now we have total number of '1'. Finding no of substring starting with '1' & ending with '1' is equivalent of choosing two '1's out of total no of '1's (count). We are not at all bothered how many zeros are in between those two '1'. In fact, there can be '1's in between those two '1's picked up.

Thus,

number of substrings starting with '1' & ending with '1' , whereis the frequency of '1's in the string.*count*

So for our above example:

Input string: 100110100 Number of '1's=4 Thus total number of substrings that can be formed starting with '1' & ending with '1' = (4*3)/2 = 6

**C++ implementation:**

```
#include <bits/stdc++.h>
using namespace std;
int compute(string s){
int count=0;
//counting no of '1's
for(int i=0;i<s.length();i++)
if(s[i]=='1')
count++;
//returning count choose 2
return (count*(count-1))/2;
}
int main(){
string s;
cout<<"enter your input string(binary string)\n";
cin>>s;
cout<<"no of substrings starting with '1' &";
cout<<" ending with '1' is: "<<compute(s)<<endl;
return 0;
}
```

**Output**

enter your input string(binary string) 100110100 no of substrings starting with '1' & ending with '1' is: 6need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (2)

.

need an explanation for this answer? contact us directly to get an explanation for this answer