# Count Substrings | CodeChef Solution

Hello coders, today we are going to solve Count Substrings CodeChef Solution whose Problem Code is CSUB.

Given a string S consisting of only 1s and 0s, find the number of substrings which start and end both in 1.
In this problem, a substring is defined as a sequence of continuous characters Si, Si+1, …, Sj where 1 ≤ i ≤ j ≤ N.

## Input Format

First line contains T, the number of testcases. Each testcase consists of N(the length of string) in one line and string in second line.

## Output Format

For each testcase, print the required answer in one line.

## Constraints

• 1 ≤ T ≤ 105
• 1 ≤ N ≤ 105
• Sum of over all testcases ≤ 105

Example

Sample Input

``````2
4
1111
5
10001``````

Sample Output

``````10
3``````

Explanation

#test1: All substrings satisfy.
#test2: Three substrings S[1,1], S[5,5] and S[1,5] satisfy.

## Solution – Count Substrings

### C++

```#include <iostream>
#include <bits/stdc++.h>
#define ll long long int
using namespace std;

int main() {
int t{};
cin>>t;
while(t--)
{
ll n{};
cin>>n;
string s{};
cin>>s;
ll c{};
for(int i=0;i<n;i++)
{
if(s[i]=='1')
c++;
}
cout<<(c*(c+1))/2<<endl;
}
return 0;
}
```

### Python

```# cook your dish here
t=int(input())
for i in range(0,t):
n=int(input())
lst=[str(i) for i in input()][:n]
temp=0
for i in lst:
if(i=='1'):
temp+=1
print((temp*(temp+1))//2)```

### Java

```/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner s=new Scanner(System.in);
int t=s.nextInt();
while(t-->0){
int n=s.nextInt();
String st=s.next();
long count=0;
for(int i=0;i<n;i++){
if(st.charAt(i)=='1')
count++;
}
System.out.println(count*(count+1)/2);
}
}
}
```

Disclaimer: The above Problem (Count Substrings) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.