C++ Program to Count 1’s in a sorted binary array
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.
C++
#include
using namespace std;
/* Returns counts of 1’s in arr[low..high]. The array is
assumed to be sorted in non-increasing order */
int countOnes(bool arr[], int low, int high)
{
if (high >= low)
{
// get the middle index
int mid = 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 Code */
int main()
{
bool arr[] = {1, 1, 1, 1, 0, 0, 0};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Count of 1's in given array is " << countOnes(arr, 0, n-1);
return 0;
}[tabbyending]
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
C++
using namespace std;
/* Returns counts of 1’s in arr[low..high]. The array is
assumed to be sorted in non-increasing order */
int countOnes(bool arr[], int n)
{
int ans;
int low = 0, high = n – 1;
while (low <= high) { // get the middle index
int mid = (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;
}
}
}
int main()
{
bool arr[] = { 1, 1, 1, 1, 0, 0, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Count of 1's in given array is "
<< countOnes(arr, n);
return 0;
}[tabbyending]
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!