Question

How to design an algorithm using recursion to find number of subarray contains all 0 in an array which only contains 0 or 1? For example, we have array 00, so we return 1, if we have an array 0100, we return 2. Assume the size of array >=1. How to find the recurrence relation of the algorithm? And how to express the recurrence relation as a function of n.

Answer 1

Here we need to number of subarrau which contains all 0 in array which contains only 0 or 1.

Basically we need to find the number of subgroups of array which contains zeros

Input: 0100 should return 2

Algorithm:

Input : arr , n // arr - array , n = array size

count = 0

IF arr[0] = 0

then count ++

FOR i=0 ; i<n-1 ;i++

IF arr[i] = 1 and arr[i+1] = 0  

THEN count++

return COUNT

In the above algorithm we are just scanning the array and counting number of occurences of 1 followed by 0 in given array and if arr[0] = 0 we increment count initially to 1. So by counting 10 patterns we get total subgroups.

Below is the recursive logic:

RECURSIVE ALGORITHM:

int count(arr,n):

if ( n == 1 ) return 0;

if( arr[0] == 1 && arr[1] == 0 ) return 1+count(arr+1,n-1);

else return count(arr+1,n-1);

In Main function:

IF (arr[0] ==0) print 1+count(arr,n)

ELSE print count(arr,n)

Here basically we are doing some constant work in each recursive call and calling recursive function with size 1 less than the input .

Let T(n) be time taken for arr of size N

Then recursive relation would be

T(n) = T(n-1) + c [ c = constant amount of work]

Complexity: O(n)