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:
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; } |
Java
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); } } |
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); |
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++
// 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> |
9
Time Complexity: O(n), where n is the size of the given string
Auxiliary Space: O(1)
Contact Us