Given a binary array sorted in non-increasing order, count the number of 1’s in it.
Examples:
Input: arr[] = {1, 1, 0, 0, 0, 0, 0}
Output: 2
Input: arr[] = {1, 1, 1, 1, 1, 1, 1}
Output: 7
Input: arr[] = {0, 0, 0, 0, 0, 0, 0}
Output: 0
A simple solution is to linearly traverse the array. The time complexity of the simple solution is O(n). We can use Binary Search to find count in O(Logn) time. The idea is to look for last occurrence of 1 using Binary Search. Once we find the index last occurrence, we return index + 1 as count.
The following is the implementation of above idea.
Javascript
<script> // Javascript program to count one's in a boolean array /* Returns counts of 1's in arr[low..high]. The array is assumed to be sorted in non-increasing order */function countOnes( arr, low, high) { if (high >= low) { // get the middle index let mid = Math.trunc(low + (high - low)/2); // check if the element at middle index is last 1 if ( (mid == high || arr[mid+1] == 0) && (arr[mid] == 1)) return mid+1; // If element is not last 1, recur for right side if (arr[mid] == 1) return countOnes(arr, (mid + 1), high); // else recur for left side return countOnes(arr, low, (mid -1)); } return 0; } // Driver program let arr = [ 1, 1, 1, 1, 0, 0, 0 ]; let n = arr.length; document.write("Count of 1's in given array is " + countOnes(arr, 0, n-1)); </script> |
Output
Count of 1's in given array is 4
Time complexity of the above solution is O(Logn)
Space complexity o(log n) (function call stack)
The same approach with iterative solution would be
Javascript
<script> /* Returns counts of 1's in arr[low..high]. The array is assumed to be sorted in non-increasing order */ function countOnes(arr,n) { let ans; let low = 0, high = n - 1; while (low <= high) { // get the middle index let mid = Math.floor((low + high) / 2); // else recur for left side if (arr[mid] < 1) high = mid - 1; // If element is not last 1, recur for right side else if (arr[mid] > 1) low = mid + 1; else // check if the element at middle index is last 1 { if (mid == n - 1 || arr[mid + 1] != 1) return mid + 1; else low = mid + 1; } } } let arr=[ 1, 1, 1, 1, 0, 0, 0]; let n = arr.length; document.write( "Count of 1's in given array is "+ countOnes(arr, n)); // This code is contributed by unknown2108 </script> |
Output
Count of 1's in given array is 4
Time complexity of the above solution is O(Logn)
Space complexity is O(1)
Please refer complete article on Count 1’s in a sorted binary array for more details!
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!
