How to find the number of zeros in Python
The problem statement is: ” An array of 0s and 1s is given. The array is sorted in decreasing order that is all the 1s followed by all the 0s. Calculate the number of zeros in Python.”
Approach 1 :
We can linearly traverse on an array to find the first occurrence of a zero. If the first occurrence of zero is found at i-th index. Then, the number of zeros is equal to the length of the array – ith index.
That is len(arr)- i-th index.
This will take O(n) time complexity in the worst-case scenario.
def countNumberOfZeroes(arr, n): flag= 0 pos= 0 count = 0 for i in range(n): if arr[i] is 0: flag=1 pos=i break if flag is 1: count = n-pos return count arr = [1, 1, 1, 0, 0, 0, 0, 0] n = len(arr) print("Count of zeroes is", countNumberOfZeroes(arr, n))
The output for the above code is:
Count of zeroes is 5
We can find the first occurrence of the zero from the binary search approach. This will take the O(logn) time complexity if n is the size of an input array.
To find the first occurrence of the zero, we first find the mid element. Now if arr[mid]= 0 and arr[mid-1]=1. This implies that the mid position is the position of the occurrence of the zero.
Now, if mid=0 and arr[mid]=0, then the first occurrence of the zero is 0th position only.
We have to understand that if the middle element is 1, then elements lying to the left of it will also be 1. Therefore, we don’t need to work on the left portion of an array. Make low=mid+1.
Similarly, if the middle element( or the mid element) of an array is 0, then the elements lying to the left will also be 0. Since we need to find the first occurrence of zero, high = mid -1 .
=def firstOccurenceOfZero(arr,low,high): while(low<=high): mid = int((high + low) / 2) if (( mid == 0 or arr[mid-1] == 1) and arr[mid] == 0): return mid if (arr[mid] == 1): low = mid+1 else: high = mid-1 return -1 def countNumberOfZeroes(arr, n): ans = firstOccurenceOfZero(arr,0,n-1) if ans is -1: return 0 else: return (n-ans) arr = [1, 1, 0, 0, 0, 0, 0, 0] n = len(arr) print("Count of zeroes is", countNumberOfZeroes(arr, n))
The output of the above code is:
Count of zeroes is 6
Also read: Efficient program to calculate e^x in Python