Given a binary string, count the number of substrings that start and end with 1.
Examples:
Input: “00100101”
Output: 3
Explanation: three substrings are “1001”, “100101” and “101”Input: “1001”
Output: 1
Explanation: one substring “1001”
Count of substrings that start and end with 1 in given Binary String using Nested Loop:
A Simple Solution is to run two loops. Outer loops pick every 1 as a starting point and the inner loop searches for ending 1 and increments count whenever it finds 1.
Below is the implementation of above approach:
C++
// A simple C++ program to count number of// substrings starting and ending with 1#include <iostream>using namespace std;int countSubStr(char str[]){ int res = 0; // Initialize result // Pick a starting point for (int i = 0; str[i] != '\0'; i++) { if (str[i] == '1') { // Search for all possible ending point for (int j = i + 1; str[j] != '\0'; j++) if (str[j] == '1') res++; } } return res;}// Driver program to test above functionint main(){ char str[] = "00100101"; cout << countSubStr(str); return 0;} |
Java
// A simple Java program to count number of// substrings starting and ending with 1class CountSubString { int countSubStr(char str[], int n) { int res = 0; // Initialize result // Pick a starting point for (int i = 0; i < n; i++) { if (str[i] == '1') { // Search for all possible ending point for (int j = i + 1; j < n; j++) { if (str[j] == '1') res++; } } } return res; } // Driver program to test the above function public static void main(String[] args) { CountSubString count = new CountSubString(); String string = "00100101"; char str[] = string.toCharArray(); int n = str.length; System.out.println(count.countSubStr(str, n)); }} |
Python3
# A simple Python 3 program to count number of# substrings starting and ending with 1def countSubStr(st, n): # Initialize result res = 0 # Pick a starting point for i in range(0, n): if (st[i] == '1'): # Search for all possible ending point for j in range(i+1, n): if (st[j] == '1'): res = res + 1 return res# Driver program to test above functionst = "00100101"list(st)n = len(st)print(countSubStr(st, n), end="")# This code is contributed# by Nikita Tiwari. |
C#
// A simple C# program to count number of// substrings starting and ending with 1using System;class GFG { public virtual int countSubStr(char[] str, int n) { int res = 0; // Initialize result // Pick a starting point for (int i = 0; i < n; i++) { if (str[i] == '1') { // Search for all possible // ending point for (int j = i + 1; j < n; j++) { if (str[j] == '1') { res++; } } } } return res; } // Driver Code public static void Main(string[] args) { GFG count = new GFG(); string s = "00100101"; char[] str = s.ToCharArray(); int n = str.Length; Console.WriteLine(count.countSubStr(str, n)); }}// This code is contributed by Shrikant13 |
PHP
<?php // A simple PHP program to count number of // substrings starting and ending with 1 function countSubStr($str) { $res = 0; // Initialize result // Pick a starting point for ($i = 0; $i < strlen($str); $i++) { if ($str[$i] == '1') { // Search for all possible // ending point for ($j = $i + 1; $j < strlen($str); $j++) if ($str[$j] == '1') $res++; } } return $res; } // Driver Code$str = "00100101"; echo countSubStr($str); // This code is contributed by ita_c?> |
Javascript
<script>// A simple javascript program to count number of // substrings starting and ending with 1 function countSubStr(str,n) { let res = 0; // Initialize result // Pick a starting point for (let i = 0; i<n; i++) { if (str[i] == '1') { // Search for all possible ending point for (let j = i + 1; j< n; j++) { if (str[j] == '1') res++; } } } return res; } // Driver program to test the above function let string = "00100101"; let n=string.length; document.write(countSubStr(string,n)); // This code is contributed by rag2127 </script> |
Output
3
Time Complexity: O(N2),
Auxiliary Space: O(1)
Count of substrings that start and end with 1 in a given Binary String using Subarray count:
We know that if count of 1’s is m, then there will be m * (m – 1) / 2 possible subarrays.
Follow the steps to solve the problem:
- Count the number of 1’s. Let the count of 1’s be m.
- Return m(m-1)/2
Below is the implementation of above approach:
C++
// A O(n) C++ program to count number of// substrings starting and ending with 1#include <iostream>using namespace std;int countSubStr(char str[]){ int m = 0; // Count of 1's in input string // Traverse input string and count of 1's in it for (int i = 0; str[i] != '\0'; i++) { if (str[i] == '1') m++; } // Return count of possible pairs among m 1's return m * (m - 1) / 2;}// Driver program to test above functionint main(){ char str[] = "00100101"; cout << countSubStr(str); return 0;} |
Java
// A O(n) Java program to count number of substrings// starting and ending with 1class CountSubString { int countSubStr(char str[], int n) { int m = 0; // Count of 1's in input string // Traverse input string and count of 1's in it for (int i = 0; i < n; i++) { if (str[i] == '1') m++; } // Return count of possible pairs among m 1's return m * (m - 1) / 2; } // Driver program to test the above function public static void main(String[] args) { CountSubString count = new CountSubString(); String string = "00100101"; char str[] = string.toCharArray(); int n = str.length; System.out.println(count.countSubStr(str, n)); }} |
Python3
# A Python3 program to count number of# substrings starting and ending with 1def countSubStr(st, n): # Count of 1's in input string m = 0 # Traverse input string and # count of 1's in it for i in range(0, n): if (st[i] == '1'): m = m + 1 # Return count of possible # pairs among m 1's return m * (m - 1) // 2# Driver program to test above functionst = "00100101"list(st)n = len(st)print(countSubStr(st, n), end="")# This code is contributed# by Nikita Tiwari. |
C#
// A O(n) C# program to count// number of substrings starting// and ending with 1using System;class GFG { int countSubStr(char[] str, int n) { int m = 0; // Count of 1's in // input string // Traverse input string and // count of 1's in it for (int i = 0; i < n; i++) { if (str[i] == '1') m++; } // Return count of possible // pairs among m 1's return m * (m - 1) / 2; } // Driver Code public static void Main(String[] args) { GFG count = new GFG(); String strings = "00100101"; char[] str = strings.ToCharArray(); int n = str.Length; Console.Write(count.countSubStr(str, n)); }}// This code is contributed by princiraj |
PHP
<?php // A simple PHP program to count number of // substrings starting and ending with 1 function countSubStr($str) { $m = 0; // Initialize result // Pick a starting point for ($i = 0; $i < strlen($str); $i++) { if ($str[$i] == '1') { $m++; } } // Return count of possible // pairs among m 1's return $m * ($m - 1) / 2;}// Driver Code$str = "00100101";echo countSubStr($str);// This code is contributed // by Akanksha Rai?> |
Javascript
<script>// A O(n) javascript program to count number of substrings//starting and ending with 1 function countSubStr(str,n) { let m = 0; // Count of 1's in input string // Traverse input string and count of 1's in it for (let i = 0; i < n; i++) { if (str[i] == '1') m++; } // Return count of possible pairs among m 1's return m * Math.floor((m - 1) / 2); } // Driver program to test the above function let str = "00100101"; let n = str.length; document.write(countSubStr(str, n)); // This code is contributed by avanitrachhadiya2155</script> |
Output
3
Time Complexity: O(N), where n is the length of the string.
Auxiliary Space: O(1).
Count of substrings that start and end with 1 in given Binary String using Recursion:
This approach is the same as the above approach but here to calculate the count of 1s we use recursion.
Follow the steps to solve the problem:
- Count the number of 1’s using recursion. Let the count of 1’s be m.
- Return m(m-1)/2
Below is the implementation of above approach:
C++
// A O(n) C++ program to count number of// substrings starting and ending with 1#include <bits/stdc++.h>using namespace std;int helper(int n, char str[], int i){ // if 'i' is on the last index if (i == n - 1) return (str[i] == '1') ? 1 : 0; // if current char is 1 // add 1 to the answer if (str[i] == '1') return 1 + helper(n, str, i + 1); // if it is zero else return helper(n, str, i + 1);}int countSubStr(char str[]){ int n = strlen(str); // counting the number of 1's in the string int count = helper(n, str, 0); // return the number of combinations return (count * (count - 1)) / 2;}// Driver program to test above functionint main(){ char str[] = "00100101"; cout << countSubStr(str); return 0;}// this code is contributed by rajdeep999 |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { static int helper(int n, char str[], int i) { // if 'i' is on the last index if (i == n - 1) return (str[i] == '1') ? 1 : 0; // if current char is 1 // add 1 to the answer if (str[i] == '1') return 1 + helper(n, str, i + 1); // if it is zero else return helper(n, str, i + 1); } static int countSubStr(char str[]) { int n = str.length; // counting the number of 1's in the string int count = helper(n, str, 0); // return the number of combinations return (count * (count - 1)) / 2; } public static void main (String[] args) { char str[] = "00100101".toCharArray(); System.out.println(countSubStr(str)); }}// This code is contributed by aadityaburujwale. |
Python3
class GFG : @staticmethod def helper( n, str, i) : # if 'i' is on the last index if (i == n - 1) : return 1 if (str[i] == '1') else 0 # if current char is 1 # add 1 to the answer if (str[i] == '1') : return 1 + GFG.helper(n, str, i + 1) else : return GFG.helper(n, str, i + 1) @staticmethod def countSubStr( str) : n = len(str) # counting the number of 1's in the string count = GFG.helper(n, str, 0) # return the number of combinations return int((count * (count - 1)) / 2) @staticmethod def main( args) : str = list("00100101") print(GFG.countSubStr(str)) if __name__=="__main__": GFG.main([]) # This code is contributed by aadityaburujwale. |
C#
// Include namespace systemusing System;public class GFG{ public static int helper(int n, char[] str, int i) { // if 'i' is on the last index if (i == n - 1) { return (str[i] == '1') ? 1 : 0; } // if current char is 1 // add 1 to the answer if (str[i] == '1') { return 1 + GFG.helper(n, str, i + 1); } else { return GFG.helper(n, str, i + 1); } } public static int countSubStr(char[] str) { var n = str.Length; // counting the number of 1's in the string var count = GFG.helper(n, str, 0); // return the number of combinations return (int)((count * (count - 1)) / 2); } public static void Main(String[] args) { char[] str = "00100101".ToCharArray(); Console.WriteLine(GFG.countSubStr(str)); }}// This code is contributed by aadityaburujwale. |
Javascript
// A O(n) JS program to count number of// substrings starting and ending with 1function helper(n, str, i) { // if 'i' is on the last index if (i == n - 1) { return (str[i] == '1') ? 1 : 0; } // if current char is 1 // add 1 to the answer if (str[i] == '1') { return 1 + helper(n, str, i + 1); } // if it is zero else { return helper(n, str, i + 1); }}function countSubStr(str) { let n = str.length; // counting the number of 1's in the string let count = helper(n, str, 0); // return the number of combinations return (count * (count - 1)) / 2;}// Driver program to test above functionconsole.log(countSubStr("00100101"));// This code is contributed by akashish_ |
Output
3
Time Complexity: O(N), Traversing over the string of size N
Auxiliary Space: O(N), for recursion call stack
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
