Count of substrings of a Binary string containing only 1s

Given a binary string of length N, we need to find out how many substrings of this string contain only 1s.

Examples: 

Input: S = "0110111"
Output: 9
Explanation:
There are 9 substring with only 1's characters. 
"1" comes 5 times. 
"11" comes 3 times. 
"111" comes 1 time.

Input: S = "000"
Output: 0

The_Approach:   the approach simple we will going to traverse over array and count one follow the steps.

•    initialize total=0 and currone=0.
•    then traverse over string and count ones in string till zero occur.
•    if zero occur then just add the number of possible substring that are possible from currone as.
•    total+=(currone*(currone+1))/2. and after addition currone=0.
•    do this till n-1.

Below is the implementation of the above approach:

#include <bits/stdc++.h> #include <iostream> using namespace std; int main() {  // Given string.  string s = "0110111";  // to avoid int overflow.  int mod = 1000000007;  long long int total = 0;  long long int one = 0;  // traverse over string.  for (int i = 0; i < s.size(); i++) {  // count the ones.  if (s[i] == '1') {  ++one;  }  else {  long long x = (one * (one + 1)) % mod;  total += x / 2;  one = 0;  }  }  // count if reamin.  if (one != 0)  total += (long long)(one * (one + 1)) / 2;  // printing the output.  cout << total << endl;  return 0; } 

import java.util.*; public class GFG {  public static void main(String[] args) {  // Given string.  String s = "0110111";  // To avoid integer overflow.  long mod = 1000000007;  long total = 0;  long one = 0;    // Traverse over the string.  for (int i = 0; i < s.length(); i++) {  // Count the ones.  if (s.charAt(i) == '1') {  one++;  } else {  long x = (one * (one + 1)) % mod;  total += x / 2;  one = 0;  }  }    // Count if remaining ones.  if (one != 0) {  total += (long) (one * (one + 1)) / 2;  }    // Printing the output.  System.out.println(total);  } } 

# Given string s = "0110111" # to avoid int overflow mod = 1000000007 total = 0 one = 0 # traverse over string for i in range(len(s)): # count the ones if s[i] == '1': one += 1 else: x = (one * (one + 1)) % mod total += x // 2 one = 0 # count if remain if one != 0: total += (one * (one + 1)) // 2 # printing the output print(total) 

using System; class Program {  static void Main()  {  // Given string.  string s = "0110111";  // to avoid int overflow.  int mod = 1000000007;  long total = 0;  long one = 0;  // traverse over string.  for (int i = 0; i < s.Length; i++)   {  // count the ones.  if (s[i] == '1') {  ++one;  }  else {  long x = (one * (one + 1)) % mod;  total += x / 2;  one = 0;  }  }  // count if reamin.  if (one != 0)  total += (long)(one * (one + 1)) / 2;  // printing the output.  Console.WriteLine(total);  } } // This code is contributed by user_dtewbxkn77n 

// Given string. let s = "0110111"; // to avoid int overflow. let mod = 1000000007; let total = 0; let one = 0; // traverse over string. for (let i = 0; i < s.length; i++) {  // count the ones.  if (s[i] == '1') {  ++one;  }  else {  let x = (one * (one + 1)) % mod;  total += x / 2;  one = 0;  } } // count if remain. if (one != 0)  total += (one * (one + 1)) / 2; // printing the output. console.log(total); 

9 

Complexity Analysis:

Time Complexity : O(n).

Auxiliary Space : O(1).

Approach: The idea is to traverse the binary string and count the consecutive ones in the string. Below is the illustration of the approach:

• Traverse the given binary string from index 0 to length - 1
• Count the number of consecutive "1" till index i.
• For each new character str[i], there will be more substring with all character's as "1"

Below is the implementation of the above approach:

// C++ implementation to find  // count of substring containing  // only ones  #include <bits/stdc++.h>  using namespace std;  // Function to find the total number  // of substring having only ones  int countOfSubstringWithOnlyOnes(string s)  {   int res = 0, count = 0;   for (int i = 0; i < s.length(); i++) {   count = s[i] == '1' ? count + 1 : 0;   res = (res + count);   }   return res;  }  // Driver Code  int main()  {   string s = "0110111";   cout << countOfSubstringWithOnlyOnes(s)   << endl;   return 0;  }  

// Java implementation to find  // count of substring containing  // only ones  class GFG{    // Function to find the total number  // of substring having only ones  static int countOfSubstringWithOnlyOnes(String s)  {   int res = 0, count = 0;   for(int i = 0; i < s.length(); i++)   {   count = s.charAt(i) == '1' ? count + 1 : 0;   res = (res + count);   }   return res;  }  // Driver code  public static void main(String[] args)  {   String s = "0110111";     System.out.println(countOfSubstringWithOnlyOnes(s));  }  }  // This code is contributed by dewantipandeydp  

# Python3 implementation to find  # count of substring containing  # only ones  # Function to find the total number  # of substring having only ones  def countOfSubstringWithOnlyOnes(s): count = 0 res = 0 for i in range(0,len(s)): if s[i] == '1': count = count + 1 else: count = 0; res = res + count return res # Driver Code  s = "0110111" print(countOfSubstringWithOnlyOnes(s)) # This code is contributed by jojo9911  

// C# implementation to find count // of substring containing only ones  using System; class GFG{    // Function to find the total number  // of substring having only ones  static int countOfSubstringWithOnlyOnes(string s)  {   int res = 0, count = 0;     for(int i = 0; i < s.Length; i++)   {   count = s[i] == '1' ? count + 1 : 0;   res = (res + count);   }   return res;  }  // Driver code  public static void Main(string[] args)  {   string s = "0110111";     Console.Write(countOfSubstringWithOnlyOnes(s));  }  }  // This code is contributed by rutvik_56 

<script> // Javascript implementation to find  // count of substring containing  // only ones  // Function to find the total number  // of substring having only ones  function countOfSubstringWithOnlyOnes(s)  {   var res = 0, count = 0;   for (var i = 0; i < s.length; i++) {   count = s[i] == '1' ? count + 1 : 0;   res = (res + count);   }   return res;  }  // Driver Code  var s = "0110111";  document.write( countOfSubstringWithOnlyOnes(s)); </script> 

9 

Time Complexity: O(n), where n is the size of the given string
Auxiliary Space: O(1)