### PROBLEM LINK:

**Author:** Lalit Kundu

**Tester:** Shang Jingbo and Gerald Agapov

**Editorialist:** Devendra Agarwal

### DIFFICULTY:

Cakewalk

### PREREQUISITES:

Adhoc

### 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 x_{1} , x_{2}, … , x_{n} position in the string then all substring starting from x_{i} and ending at x_{j} 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.