Given a binary string S. The task is to count the number of substrings that start and end with 1. For example, if the input string is “00100101”, then there are three substrings “1001”, “100101” and “101”.
Example 1:
Input:
N = 4
S = 1111
Output: 6
Explanation: There are 6 substrings from
the given string. They are 11, 11, 11,
111, 111, 1111.
Example 2:
Input:
N = 5
S = 01101
Output: 3
Explanation: There 3 substrings from the
given string. They are 11, 101, 1101.
Your Task:
The task is to complete the function binarySubstring() which takes the length of binary string n and a binary string a as input parameter and counts the number of substrings starting and ending with 1 and returns the count.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ |S| ≤ 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    
    #Function to count the number of substrings that start and end with 1.
    def binarySubstring(self,n,s):
        #code here

Solutions:
class Solution:

	def binarySubstring(self, n, s):
		ans = lambda x: x * (x - 1) // 2
		no_1 = 0
		for i in s:
			if i == '1':
				no_1 += 1
		return ans(no_1)


class Solution:

	def binarySubstring(self, n, s):
		count = 0
		for i in s:
			if i == '1':
				count += 1
		return count * (count - 1) // 2


class Solution:

	def binarySubstring(self, n, s):
		total = 0
		m = s.count('1')
		total = m * (m - 1) // 2
		return total


class Solution:

	def binarySubstring(self, n, s):
		c = s.count('1')
		total = 0
		for i in range(0, c):
			total += i
		return total


class Solution:

	def binarySubstring(self, n, s):
		count = 0
		for c in s:
			if c == '1':
				count = count + 1
		return int(count * (count - 1) / 2)


class Solution:

	def binarySubstring(self, n, s):
		l = 0
		for i in range(n):
			if s[i] == '1':
				l += 1
		x = l * (l - 1) / 2
		return int(x)


class Solution:

	def binarySubstring(self, n, s):
		c = s.count('1')
		return c * (c - 1) // 2


class Solution:

	def binarySubstring(self, n, s):
		m = 0
		for i in range(0, n):
			if s[i] == '1':
				m = m + 1
		return m * (m - 1) // 2


class Solution:

	def binarySubstring(self, n, s):
		ind = []
		for i in range(n):
			if s[i] == '1':
				ind.append(i)
		return len(ind) * (len(ind) - 1) // 2


class Solution:

	def binarySubstring(self, n, s):
		fcount = 0
		ffcount = 0
		count = -1
		for i in range(n):
			if s[i] == '1':
				count += 1
				fcount += count
				ffcount += fcount
		return fcount


class Solution:

	def binarySubstring(self, n, s):
		cnt = s.count('1')
		return cnt * (cnt - 1) // 2


import re

class Solution:

	def binarySubstring(self, n, s):
		count = len(re.findall('1', s))
		return count * (count - 1) // 2


class Solution:

	def binarySubstring(self, n, s):
		ct = s.count('1')
		return ct * (ct - 1) // 2


class Solution:

	def binarySubstring(self, n, s):
		o = s.count('1')
		o -= 1
		if o == 0:
			return 0
		return o * (o + 1) // 2


class Solution:

	def binarySubstring(self, n, s):
		(k, l) = (0, 0)
		for i in range(n):
			if s[i] == '1':
				k += l
				l += 1
		return k


class Solution:

	def binarySubstring(self, n, s):
		a = s.count('1')
		m = a * (a - 1) // 2
		return m


class Solution:

	def binarySubstring(self, n, s):
		count = 0
		n = len(s)
		ones_count = 0
		for i in range(n):
			if s[i] == '1':
				ones_count += 1
				count += ones_count - 1
		return count


class Solution:

	def binarySubstring(self, n, s):
		c = 0
		for i in range(0, n):
			if s[i] == str(1):
				c = c + 1
		d = c * (c - 1) // 2
		return d


class Solution:

	def binarySubstring(self, n, s):
		ans = 0
		for i in s:
			if i == '1':
				ans += 1
		b = ans * (ans - 1) // 2
		return b


class Solution:

	def binarySubstring(self, n, s):
		temp = s.count('1')
		return temp * (temp - 1) // 2


import math

class Solution:

	def binarySubstring(self, n, s):
		c = s.count('1')
		if c > 1:
			res = math.factorial(c) // (math.factorial(2) * math.factorial(c - 2))
		else:
			res = 0
		return res


class Solution:

	def binarySubstring(self, n, s):
		N = s.count('1')
		ans = N * (N - 1) // 2
		return ans


class Solution:

	def binarySubstring(self, n, s):
		count = 0
		total_strings = 0
		first_1_found = False
		for i in range(0, n):
			if s[i] == '1':
				if first_1_found:
					count += 1
					total_strings += count
				if not first_1_found:
					first_1_found = True
		return total_strings


class Solution:

	def binarySubstring(self, n, s):
		suffix = []
		se = 0
		for i in range(n):
			if s[n - i - 1] == '1':
				se += 1
			suffix.append(se)
		x = suffix[-1]
		suffix = suffix[::-1]
		ans = 0
		for i in range(n):
			if s[i] == '1':
				ans += x - suffix[i]
		return ans


import math

class Solution:

	def binarySubstring(self, n, s):
		string = list(s)
		nunu = string.count('1')
		if nunu >= 2:
			num = math.factorial(nunu)
			den1 = math.factorial(nunu - 2)
			return int(num / (den1 * 2))
		else:
			return 0


class Solution:

	def binarySubstring(self, n, s):
		cnt = 0
		for each in s:
			if each == '1':
				cnt += 1
		return cnt * (cnt - 1) // 2


class Solution:

	def binarySubstring(self, n, s):
		s1 = ''
		for i in s:
			if i == '1':
				s1 += i
		k = len(s1)
		return k * (k - 1) // 2


class Solution:

	def binarySubstring(self, n, s):
		t = s.count('1')
		return t * (t - 1) // 2


import math

class Solution:

	def binarySubstring(self, n, s):
		c1 = 0
		c2 = 0
		for i in s:
			if i == '1':
				c1 = c1 + 1
		return c1 * (c1 - 1) // 2


class Solution:

	def binarySubstring(self, n, s):
		(x, y) = (0, 0)
		for i in range(n):
			if s[i] == '1':
				x += y
				y += 1
		return x


class Solution:

	def binarySubstring(self, n, s):
		counter = 0
		for x in s:
			if x == '1':
				counter += 1
		return counter * (counter - 1) // 2


class Solution:

	def binarySubstring(self, n, s):
		num_of_ones = 0
		for ele in s:
			if ele == '1':
				num_of_ones += 1
		return num_of_ones * (num_of_ones - 1) // 2


class Solution:

	def binarySubstring(self, n, s):
		if n <= 0:
			return 0
		else:
			counter = 0
			for i in range(n):
				if s[i] == '1':
					counter += 1
			return counter * (counter - 1) // 2


class Solution:

	def binarySubstring(self, n, s):
		count_1s = 0
		for i in s:
			if i == '1':
				count_1s += 1
		substr1to1 = count_1s * (count_1s - 1) // 2
		return substr1to1


class Solution:

	def binarySubstring(self, n, s):
		ones = 0
		for i in range(len(s)):
			if s[i] == '1':
				ones += 1
		return ones * (ones - 1) // 2


class Solution:

	def factorial(n):
		s = 1
		for i in range(1, n):
			s = s * i
		return s

	def binarySubstring(self, n, s):
		count = 0
		for i in range(len(s)):
			if s[i] == '1':
				count += 1
		num = 1
		for i in range(1, count + 1):
			num = num * i
		den = 1
		for i in range(1, count - 1):
			den = den * i
		x = num / (den * 2)
		return int(x)