CareerCup

/**
	 * This method divides the array into halves and calls recursively
	 * for the count. countZeros will count the zeros that go 
	 * across left and right
	 */
	private static int getConsecutiveZeroCount(int [] inputArray,int lo,int hi) {
		int mid = lo + (hi-lo)/2;
        if (hi <= lo) return 0;
		int count = getConsecutiveZeroCount(inputArray, lo, mid);
		count +=getConsecutiveZeroCount(inputArray, mid+1, hi);
		return count+countZeros(inputArray,lo,hi,mid);
	}
	/**
	 * This method will count any zeros between left and right array
	 * @return
	 */
	private static int countZeros(int [] inputArray,int lo, int hi,int mid) {
		if(inputArray[mid+1] == 0 && inputArray[mid] == 0) return 1;
		return 0;
	}
	public static void  main(String[] args) {
		int [] inputArray = new int[]{3, 0, 0, 1, 0, 1, 3, 2, 0, 0, 0, 1, 2};
		System.out.println(getConsecutiveZeroCount(inputArray, 0, inputArray.length-1));
	}

Not sure why a divide and conquer approach would be requested- the problem can be solved easily enough in a linear fashion with O(n) complexity and O(1) memory:

public static int countConsecutive0s(int[] arr){
	int counter = 0;
	for(int i = 1; i < arr.length; i++){
		if(arr[i-1] == 0 && arr[i] == 0){
			counter++;
		}
	}
	return counter;
}

However, if you had to do a divide and conquer approach specifically like if you were doing some GPU work, then you could do it like the following (pseudo coded up from the perspective of each core)

linearly count consecutive 0s in assigned section
if(not the first section in the array)
if(section starts with 0 and previous section ends with 0){
add 1 to count
}
}
save the counts to a working buffer
use logarithmic compression to sum all the counts from the different cores

Runtime complexity will by O(n / c + c log c) where c is the number of cores and memory is O(c)

Above code is generic so you can make to check only fir zeros

You just need to use a binary search over the array looking for zeros. Whenever it finds one, just check whether the element to the right is also a zero.

Note however that you do not gain anything by using divide and conquer in this problem. It may incur additional cost even, since the DaC paradigm brings in more space complexity due to the call stack.

An implementation in C:

int count(const int *V, int s, int e, int n)
{
	if (e < s) return 0;

	int counter = 0;
	int mid_idx = (s+e)/2;

	if (V[mid_idx] == 0) {
		if (mid_idx < n && V[mid_idx+1] == 0) {
			++counter;
		}
	}

	return counter + count(V, s, mid_idx-1, n) + 
		count(V, mid_idx+1, e, n);
}

int main(int argc, char *argv[])
{
	int V[] = {3, 0, 0, 1, 0, 1, 3, 2, 0, 0, 0, 1, 2};
	int n = sizeof(V)/sizeof(int);

	printf("%d\n", count(V, 0, n-1, n-1));
	return 0;
}

Why can't we forward and backward linear search simultaneously. When we the center break the loop.

#include <iostream>
#include <cstdio>

using namespace std;

int across(int arr[], int mid, int l, int h) {
	int count = 0;
	if (arr[mid] == 0) {
		if (mid - 1 >= l && arr[mid - 1] == 0) {
			count++;
		}
		if (mid + 1 <= h && arr[mid + 1] == 0) {
			count++;
		}		
	}
	return count;
}

int countConsec(int arr[], int l, int h) {
	if (l > h) {
		return 0;
	}
	int mid = (l + h) / 2;
	int count;
	int a = countConsec(arr, l, mid - 1);
	int b = countConsec(arr, mid + 1, h);
	int c = across(arr, mid, l, h);
	count = a + b + c;
	return count;
}

int main() {
	int arr[] = {3, 0, 0, 1, 0, 1, 3, 2, 0, 0, 0, 1, 2};
	cout << countConsec(arr, 0, 12) << endl;
	return 0;
}

Python 3

def consecutive_zeros(lst):
    pairs = 0
    for i, y in enumerate(lst):
        try:
            if y == 0:
                if lst[i + 1] == 0:
                    pairs += 1
        except IndexError:
            pass
    return pairs

print(consecutive_zeros([3, 0, 0, 1, 0, 1, 3, 2, 0, 0, 0, 1, 2]))  # 3