Count Substrings | CodeChef Solution

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

Task

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 S_i, S_i+1, …, S_j 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 ≤ 10⁵
• 1 ≤ N ≤ 10⁵
• Sum of N over all testcases ≤ 10⁵

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() {
	// your code goes here
	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
	{
		// your code goes here
		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.