Count of substrings of a Binary string containing only 1s

0 0 4 minutes read

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:

C++

#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;
}

Python3

# 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)

C#

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

Javascript

// 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);

Output

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++

// 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

// 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

# 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#

// 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

Javascript

<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>

Output

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

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!