top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Find the number of zeroes in an array in C/C++

+1 vote
394 views

Given an array of 1s and 0s which has all 1s first followed by all 0s. Find the number of 0s. Count the number of zeroes in the given array.

posted Apr 8, 2014 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes
// A divide and conquer solution to find count of zeroes in an array
// where all 1s are present before all 0s
#include <stdio.h>

/* if 0 is present in arr[] then returns the index of FIRST occurrence
   of 0 in arr[low..high], otherwise returns -1 */
int firstZero(int arr[], int low, int high)
{
    if (high >= low)
    {
        // Check if mid element is first 0
        int mid = low + (high - low)/2;
        if (( mid == 0 || arr[mid-1] == 1) && arr[mid] == 0)
            return mid;

        if (arr[mid] == 1)  // If mid element is not 0
            return firstZero(arr, (mid + 1), high);
        else  // If mid element is 0, but not first 0
            return firstZero(arr, low, (mid -1));
    }
    return -1;
}

// A wrapper over recursive function firstZero()
int countOnes(int arr[], int n)
{
    // Find index of first zero in given array
    int first = firstZero(arr, 0, n-1);

    // If 0 is not present at all, return 0
    if (first == -1)
        return 0;

    return (n - first);
}

/* Driver program to check above functions */
int main()
{
    int arr[] =   {1, 1, 1, 0, 0, 0, 0, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Count of zeroes is %d", countOnes(arr, n));
    return 0;
}
Output:

Count of zeroes is 5 
answer Dec 1, 2014 by Shivaranjini
Similar Questions
+5 votes

Given an unsorted array, find the max length of subsequence in which the numbers are in incremental order.

For example: If the input array is {7, 2, 3, 1, 5, 8, 9, 6}, a subsequence with the most numbers in incremental order is {2, 3, 5, 8, 9} and the expected output is 5.

0 votes

Suppose A is represented by 1, B by 2 ...and Z by 26.

Now we are given a number, and we need to find number of possible decoding for this number. No need to consider number starts with zero.

Example:
Input – 1234,
Output – 3(ABCD, AWD, LCD)

+7 votes

eg: array = "amber","gaura","sahil","mabre","rauag","halis", "bamre"}
then no. of anagram groups = 3.
"amber" ,"mabre" ,"bamre" form one group.

+5 votes

Help me to write a C program which can generate list of numbers which are palindrome in decimal and octal notion. You can take some max as a limit find out all numbers which satisfy the given property between 1 to n.

...