CSUB : Count Substrings

CSUB : Count Substrings

Link for the problem: CSUB

Solution:

To solve this problem, you have to focus on two points.
1.) A substring of a single character '1' is a valid string.
2.) For every character '1' in the string, every other '1' occurring before will make a valid substring with it.
So from these two points, the total number of valid substring would be 1+2+3+...+k. Where k is the total number of 1s in the string. So it is k*(k+1)/2.

Code:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
      int n;
      scanf("%d",&n);
      char s[100001];
     scanf(" %s ",s);
     long long int i,j,k,c=0;
     for(i=0;i<n;i++)
     {
         if(s[i]=='1')
         c++;
     }
     printf("%lld\n",(c*(c+1))/2);
    }
    return 0;

}