CareerCup

package careercup;

public class CC5716548811489280 {

	public static int findZeros(int[] input,int count,int start,int end){
		//System.out.println("Start"+ start);
		//System.out.println("End"+ end);
		if(start>end){
			return count+1;
		}
		int mid = (end + start)/2;
		//System.out.println("mid" + mid);
		if(input[mid] == 0){
			count = mid;
			return findZeros(input,count, mid+1, end);
		}else{
			return findZeros(input, count,start, mid-1);
		}
		
	} 
	
	public static void main(String[] args){
		int[] array = {0,0,0,0,0,0,1,1,1,1,1};
		System.out.println(findZeros(array, 0,0, array.length - 1));
	}
}

Assuming given array is sorted which means there will be series of 0's followed by 1's.

Recursive solution :
///
find_Zero_count(A,i,j)
{
if(i==j)
{
if(A[i] == 0)
return 1
else
return 0

mid = i+(j-i)/2;
if(A[mid]==0)
{
return (j-i)/2+1+find_zero_count(A, mid+1, j)
}
else
{
return find_zero_count(A,i, mid-1)
}

}
\\\

public int returnZero(int[] arr,int num,int i,int count)
{
if (i >= num) return count;
if (arr[i] == 0) count++;
else
i = num;
return returnZero(arr, num, ++i, count);
}

Simple binary search.
Recursive solution:

int zero_count(array, start, end)
{
	if (start == end)
	{
		if (array[start] == 0)
		{
			return start;
		}
		else
		{
			return start - 1;
		}
	}
	else
	{
		mid = (start + end) / 2;
		if (array[mid] == 0)
		{
			return zero_count(array, mid + 1, end);
		}
		else
		{
			return zero_count(array, start, mid);
		}
	}
}

Iterative solution:

int zero_count(array, len)
{
	start = 0;
	end = len - 1;
	while (start < end)
	{
		mid = (start + end) / 2;
		if (array[mid] == 0)
		{
			start = mid + 1;
		}
		else
		{
			end = mid;
		}
	}

	if (array[start] == 0)
	{
		return start;
	}
	else
	{
		return start - 1;
	}
}

Just use a binary search technique to find the first index of 1 in the array. Then return this index as the number of zeroes in the array

If the array is very large (e.g. stream) then binary search is not efficient. Use the following:
1) Check the value at the following points 1,2,4,8,16,32,64..... till you encounter 1
2) Now the first 1 would be in the last block e.g if A[64] is 1 then the first 1 will lie between 32 and 64
3) Perform binary search in the block (or repeat the same procedure till block size is 1)

public static int FindNumberOfZeroes(int[] array, int s, int e)
{
    if (s > e)
        return 0;

    if (s == e)
        return array[s] == 0 ? 1 : 0;

    int m = s + (e - s) / 2;

    if (array[m] == 1)
    {
        if (m > 1 && array[m - 1] == 0)
            return m;
        return FindNumberOfZeroes(array, s, m - 1);
    }
    else
    {
        if (m < array.Length - 1 && array[m + 1] == 1)
            return m + 1;
        return FindNumberOfZeroes(array, m + 1, e);
    }
}

public int numberOfOsInArray(int[] arrA){

return numberOf0(arrA, arrA.length-1);
}

private int numberOf0(int[] arrA, int i) {
if(arrA[i]==0){
return i+1;
}else{
return numberOf0(arrA,i-1);
}
}

#include<stdio.h>
#include<stdlib.h>

int count(int a[],int n)
{
  int i;
  int count=0;
  if(a[0]==0)
    {
      while(a[i++]!=1)
        {
          count++;
        }
      return count;
    }
  else
    {
      while(a[i++]!=0)
        {
          count++;
        }
      return n-count;
    }

}

main()
{
  int a[10]={0,0,0,0,1,1,1,1,1,1};
  printf("%d",count(a,10));
}

I think, following will work too.

#Recusive

public int CountZerosRecursive(int[] input, int start, int end)
        {
            if (input.Length <= 0 || (start > end)) return 0;

            int mid = (start + end) / 2;

            if (input[mid] == 0)
                return (mid-start +1) + CountZerosRecursive(input, mid + 1, end);
            else
                return CountZerosRecursive(input, start, mid - 1);
        }

#Iterative
        public int CountZerosIterative(int[] input)
        {
            if (input.Length <= 0) return -1;

            int start = 0;
            int end = input.Length - 1;

            int mid = 0;
            int count = 0;
            while(start < end)
            {
                mid = start + end / 2;
                if (input[mid] == 0)
                {
                    count = count + (mid - start + 1);
                    start = mid + 1;
                }
                else
                {
                    end = mid - 1;
                }
            }
            return count;
        }

O(n) recursive solution:

numzero(0 to n)= 1+numzero(1 to n)

int zerocount(array, startindex)
{
if(array[startindex]==1) return 0;
else
return 1+zerocount(array,startindex+1);
}

}

public static void findNo1s(Integer[] array) {
        Integer sum = 0;
        for(int i =0; i<array.length && array[i] != 0;i++) {
            sum += array[i];
        }
        System.out.println(" No of 1s = "+sum+ " no od 0s ="+(array.length-sum));
    }

// recursive solution
    public static int zeros(int[] array, int min, int max){
        
        int mid = (min+max)/2;
        
        if(mid == 0){
            return array[mid]== 0 ? 1 : 0;
        }
        
        if(array[mid] == 1){
            if(array[mid-1]==0)
                return mid;
            return zeros(array,min, mid-1); 
        }
        else {
            return zeros(array, mid+1, max);
        }
    }
    
    // iterative solution
    public static int zeros(int[] array){
        
        int len = array.length;
        int start = 0;
        int end = len-1;
        int mid;
        do{
            mid =  (start + end)/2;
            if(mid==0){
                return array[mid]==0 ? 1 : 0;
            }
            
            if(array[mid]==1){
                if(array[mid-1]==0)
                    return mid;                
                end = mid -1;
            }else{
                start = mid +1;
            }            
        }while(mid > 0);
        return 0;
    }

Using Recursion:

This is a pretty straightforward way to get to the solution.

I am exploiting two very important facts. #1 It is sorted zeros than ones. #2 You'll need to study it figure it out.

I ran a few different test cases and it passed all.

This is my first post so please prove me wrong.

int zero_count_recursive(int array[], int low, int high){

	int mid = (low+high)/2;
	
	if(array[mid] == 0){
		low = mid;
		return zero_count_recursive(array, mid, high);
	}
	else {
		if(array[mid-1] == 0){
		return mid;}
		else{
		high = mid;
		return zero_count_recursive(array,low, high);

		}

	}	

}

..If you can't figure some ghetto way to solve this problem using iteration...I can't help you. Sorry.

public static int countZeroRecursion (int[] arr, int i) {
		if(i >= arr.length) return 0;
		if(arr[i] == 1) return 0;
		return 1 + countZeroRecursion(arr, ++i);
	}
	
	public static int countZeroIterative (int[] arr) {
		int sum = 0;
		for(int i=0; i<arr.length; i++) {
			if(arr[i] == 0) ++sum; 
			else 
				break;
		}
		return sum;
	}

static void wrapperSortedArray0s1s(int a[]) {
		
		int k = sortedArray0s1s(a, 0, a.length - 1);
		System.out.println(k);
		if (k == 0) {
			System.out.println("0's = 0");
			System.out.println("1's = " + a.length);
		} else if (k == a.length - 1) {
			System.out.println("0's = " + a.length);
			System.out.println("1's = 0");
		} else {
			System.out.println("0's = " + (k + 1));
			System.out.println("1's = " + (a.length - k - 1));
		}

	}

	static int sortedArray0s1s(int a[], int l, int u) {
		
		int m = (l + u) / 2;
		if (m >= a.length - 1 || m <= 0)
			return m;
		if (a[m] == 0 && a[m + 1] > 0)
			return m;
		else if (a[m] > 0)
			return sortedArray0s1s(a, l, m - 1);
		else
			return sortedArray0s1s(a, m + 1, u);
	}