Topic: Searching
Questions Successfully Completed: 1
1) Count 1's in a binary array | Easy |
Count 1's in a binary array
Time Complexity : O(log n)
Space Complexity : O(1)
Question
Input: N = 8 arr[] = {1,1,1,1,1,0,0,0} Output: 5 Explanation: Number of 1's in given binary array: 1 1 1 1 1 0 0 0 is 5.
public static int countOnes(int arr[], int N){
int low = 0;
int high = N-1;
while(low<=high){
int mid = (low + high)/2;
if(arr[mid]==1){
if((mid == N-1)||(arr[mid+1]==0) ){
return mid+1;
}
else {
low = mid + 1;
}
}
else{
high = mid -1;
}
}
return 0;
}
Thank you for reading :)