Given an array of size N consisting of only 0's and 1's. The array is sorted in such a manner that all the 1's are placed first and then they are followed by all the 0's. Find the count of all the 0's.
Example 1:
Input:
N = 12
Arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0}
Output: 3
Explanation: There are 3 0's in the given array.
Example 2:
Input:
N = 5
Arr[] = {0, 0, 0, 0, 0}
Output: 5
Explanation: There are 5 0's in the array.
Your Task:
You don't need to read input or print anything. Your task is to complete the function countZeroes() which takes the array of integers arr[] and its size n as input parameters and returns the number of zeroes present in the array.
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{5}
0 <= Arr[i] <= 1

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Complete search

Starter code: #User function Template for python3



class Solution:

    def countZeroes(self, arr, n):

        # code here

Solutions:
class Solution:

	def countZeroes(self, arr, n):
		return n - arr.index(0)


def binary(arr):
	if len(arr) == 1:
		if arr[0] == 0:
			return 0
		else:
			return 1
	mid = len(arr) // 2
	if arr[mid] == 0 and arr[mid - 1] == 0:
		return binary(arr[:mid])
	if arr[mid] == 0 and arr[mid - 1] == 1:
		return mid
	if arr[mid] == 1:
		return mid + 1 + binary(arr[mid + 1:])

class Solution:

	def countZeroes(self, arr, n):
		i = binary(arr)
		return n - i


class Solution:

	def countZeroes(self, arr, n):
		return arr.count(0)


class Solution:

	def countZeroes(self, arr, n):
		count = 0
		for i in range(n):
			if arr[i] == 0:
				count += 1
		return count


class Solution:

	def countZeroes(self, arr, n):
		m = int(n / 2)
		l = 0
		h = n - 1
		c = 0
		while l <= h:
			if arr[m] == 1:
				if m != n - 1 and arr[m + 1] == 0:
					m = m + 1
					c = 1
					break
				else:
					l = m + 1
					m = int((l + h) / 2)
			elif arr[m] == 0:
				if m != 0 and arr[m - 1] == 1:
					c = 1
					break
				else:
					h = m - 1
					m = int((l + h) / 2)
		if c == 1:
			return n - m
		elif m == 1:
			return 0
		else:
			return n


class Solution:

	def countZeroes(self, arr, n):
		c = 0
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] == 1:
				break
			else:
				c = c + 1
		return c


class Solution:

	def countZeroes(self, arr, n):
		sum = 0
		for i in arr:
			if i == 1:
				sum += 1
		return n - sum


class Solution:

	def countZeroes(self, arr, n):
		start = 0
		end = n - 1
		count = 0
		while start <= end:
			mid = start + (end - start) // 2
			if arr[mid] == 0:
				count = n - mid
				end = mid - 1
			else:
				start = mid + 1
		return count


class Solution:

	def countZeroes(self, arr, n):
		count = 0
		for x in range(n - 1, -1, -1):
			if arr[x] == 0:
				count += 1
			else:
				break
		return count


class Solution:

	def first_zero(self, arr, high, low):
		while high >= low:
			mid = (high + low) // 2
			if (mid == 0 or arr[mid - 1] == 1) and arr[mid] == 0:
				return mid
			elif arr[mid] == 1:
				low = mid + 1
			else:
				high = mid - 1
		return -1

	def countZeroes(self, arr, n):
		index_z = self.first_zero(arr, n - 1, 0)
		if index_z == -1:
			return 0
		return n - index_z


class Solution:

	def countZeroes(self, arr, n):

		def transition(arr, i, j):
			if i > j:
				return len(arr)
			m = (i + j) // 2
			if arr[m] == 0 and arr[m - 1] == 1:
				return m
			elif arr[m] == 1 and arr[m + 1] == 0:
				return m + 1
			elif arr[m] == arr[m + 1] and arr[m] == 0:
				return transition(arr, i, m - 1)
			else:
				return transition(arr, m + 1, j)
		if arr[0] == 0:
			return n
		if n == 1:
			return 0
		return n - transition(arr, 0, n)


class Solution:

	def countZeroes(self, arr, n):
		i = 0
		for j in arr[::-1]:
			if j > 0:
				break
			i += 1
		return i


class Solution:

	def countZeroes(self, arr, n):
		total = sum(arr)
		ans = n - total
		return ans


class Solution:

	def countZeroes(self, arr, n):
		count = 0
		arr.sort(reverse=1)
		for i in range(len(arr)):
			if arr[i] == 0:
				count += 1
		return count


class Solution:

	def countZeroes(self, arr, n):
		arr.sort()
		zero = 0
		count = 0
		for num in arr:
			if zero != num:
				break
			count += 1
		return count


class Solution:

	def countZeroes(self, arr, n):
		a = list(arr)
		c = 0
		for i in range(n):
			if a[i] == 0:
				c += 1
		return c


class Solution:

	def countZeroes(self, arr, n):
		return len(arr) - sum(arr)


class Solution:

	def countZeroes(self, arr, n):
		a = 0
		b = n // 2
		c = n - 1
		while b - a > 0:
			if arr[b] == 0:
				if arr[b - 1] == 1:
					return n - b
				else:
					c = b
					b = (a + c) // 2
			elif b == n - 1:
				return 0
			else:
				a = b
				b = (a + c + 1) // 2
		if arr[b] == 1:
			return 0
		else:
			return n - b


class Solution:

	def countZeroes(self, arr, n):
		ar_len = len(arr)
		ct = 0
		for index in range(1, ar_len + 1):
			if arr[-index] == 0:
				ct += 1
			else:
				break
		return ct


class Solution:

	def countZeroes(self, arr, n):
		(l, h) = (0, n - 1)
		candidate = -1
		while l <= h:
			mid = (l + h) // 2
			if arr[mid] == 1:
				l = mid + 1
			if arr[mid] == 0:
				candidate = mid
				h = mid - 1
		if candidate == -1:
			return 0
		return n - candidate


class Solution:

	def countZeroes(self, arr, n):
		s = 0
		e = n - 1
		ans = -1
		mid = 0
		while s <= e:
			mid = (s + e) // 2
			if arr[mid] == 0:
				ans = mid
				e = mid - 1
			else:
				s = mid + 1
		return n - ans


class Solution:

	def countZeroes(self, arr, n):
		head = 0
		tail = n - 1
		while head <= tail:
			mid = (head + tail) // 2
			if arr[head] == 0:
				return n - head
			if arr[mid] == 1:
				head = mid + 1
			else:
				head += 1


class Solution:

	def countZeroes(self, arr, n):
		arr.reverse()
		if 1 in arr:
			return arr.index(1)
		return n


class Solution:

	def countZeroes(self, arr, n):
		l = -1
		r = n
		while l + 1 < r:
			m = (l + r) // 2
			if arr[m] == 1:
				l = m
			else:
				r = m
		return n - r


class Solution:

	def countZeroes(self, arr, n):
		start_index = 0
		for i in range(0, n):
			if arr[i] == 0:
				return n - i
		return 0


class Solution:

	def countZeroes(self, arr, n):
		if 1 not in arr:
			return len(arr)
		count = 0
		for i in range(n):
			if arr[i] == 1 and arr[i + 1] == 0:
				x = i
				break
		return n - 1 - x


class Solution:

	def countZeroes(self, arr, n):
		b = 0
		for x in arr:
			if x == 0:
				b += 1
		return b


class Solution:

	def countZeroes(self, arr, n):
		count = 0
		for i in arr:
			if i == 0:
				count += 1
			else:
				pass
		return count


class Solution:

	def countZeroes(self, arr, n):
		c = 0
		for e in arr[::-1]:
			if e == 0:
				c += 1
		return c


class Solution:

	def countZeroes(self, arr, n):

		def binary_search(arr):
			start = 0
			end = len(arr) - 1
			while start <= end:
				mid = (start + end) // 2
				if arr[mid] == 1 and arr[mid + 1] == 0:
					return mid
				if arr[mid] == 0 and arr[mid - 1] == 1:
					return mid - 1
				if arr[mid] == 1 and arr[mid - 1] == 1:
					start = mid + 1
				if arr[mid] == 0 and arr[mid - 1] == 0:
					end = mid - 1
			return -1
		p = binary_search(arr)
		return len(arr) - p - 1


class Solution:

	def countZeroes(self, arr, n):

		def binary_search(arr):
			start = 0
			end = len(arr) - 1
			while start <= end:
				mid = (start + end) // 2
				if arr[mid] == 1 and arr[mid + 1] == 0:
					return mid
				if arr[mid] == 0 and arr[mid - 1] == 1:
					return mid - 1
				if arr[mid] == 1 and arr[mid - 1] == 1:
					start = mid + 1
				if arr[mid] == 0 and arr[mid - 1] == 0:
					end = mid - 1
			return -1
		p = binary_search(arr)
		count = 0
		for i in range(p + 1, len(arr)):
			if arr[i] == 0:
				count += 1
		return count


class Solution:

	def binarysearch(self, arr, start, end):
		index = (start + end) // 2
		if arr[index] == 0:
			if arr[index - 1] == 1:
				return index
			else:
				return self.binarysearch(arr, start, index - 1)
		elif arr[index + 1] == 0:
			return index + 1
		else:
			return self.binarysearch(arr, index + 1, end)

	def countZeroes(self, arr, n):
		if arr[0] == 0:
			return n
		start = 0
		end = len(arr) - 1
		real_index = self.binarysearch(arr, start, end)
		return end - real_index + 1