#include <stdio.h>
 
// Function to find number of 1's in a sorted binary array
int count(int arr[], int n)
{
    // if last element of the array is 0, no ones can
    // be present in it since it is sorted
    if (arr[n - 1] == 0) {
        return 0;
    }
 
    // if first element of the array is 1, all its elements
    // are ones only since it is sorted
    if (arr[0]) {
        return n;
    }
 
    // divide array into left and right sub-array and recurse
    return count(arr, n/2) + count(arr + n/2, n - n/2);
}
 
// main function
int main(void)
{
    int arr[] = { 0, 0, 0, 0, 1, 1, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    printf("Total number of 1's present are %d", count(arr, n));
 
    return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CgovLyBGdW5jdGlvbiB0byBmaW5kIG51bWJlciBvZiAxJ3MgaW4gYSBzb3J0ZWQgYmluYXJ5IGFycmF5CmludCBjb3VudChpbnQgYXJyW10sIGludCBuKQp7CiAgICAvLyBpZiBsYXN0IGVsZW1lbnQgb2YgdGhlIGFycmF5IGlzIDAsIG5vIG9uZXMgY2FuCiAgICAvLyBiZSBwcmVzZW50IGluIGl0IHNpbmNlIGl0IGlzIHNvcnRlZAogICAgaWYgKGFycltuIC0gMV0gPT0gMCkgewogICAgICAgIHJldHVybiAwOwogICAgfQoKICAgIC8vIGlmIGZpcnN0IGVsZW1lbnQgb2YgdGhlIGFycmF5IGlzIDEsIGFsbCBpdHMgZWxlbWVudHMKICAgIC8vIGFyZSBvbmVzIG9ubHkgc2luY2UgaXQgaXMgc29ydGVkCiAgICBpZiAoYXJyWzBdKSB7CiAgICAgICAgcmV0dXJuIG47CiAgICB9CgogICAgLy8gZGl2aWRlIGFycmF5IGludG8gbGVmdCBhbmQgcmlnaHQgc3ViLWFycmF5IGFuZCByZWN1cnNlCiAgICByZXR1cm4gY291bnQoYXJyLCBuLzIpICsgY291bnQoYXJyICsgbi8yLCBuIC0gbi8yKTsKfQoKLy8gbWFpbiBmdW5jdGlvbgppbnQgbWFpbih2b2lkKQp7CiAgICBpbnQgYXJyW10gPSB7IDAsIDAsIDAsIDAsIDEsIDEsIDEgfTsKICAgIGludCBuID0gc2l6ZW9mKGFycikgLyBzaXplb2YoYXJyWzBdKTsKCiAgICBwcmludGYoIlRvdGFsIG51bWJlciBvZiAxJ3MgcHJlc2VudCBhcmUgJWQiLCBjb3VudChhcnIsIG4pKTsKCiAgICByZXR1cm4gMDsKfQ==