GATE Suitability Test | Test 1 | Question: 11

Question

Consider the following C program?

void mystery(int n){
    if(n<=0) return;
    printf("%d", 0);
    mystery(n-1);
    mystery(n-2);
}

int main(){
    int n=10;
    mystery(n);
    return 0;
}

The number of ‘0’s printed by above program is ?

Comments

T(n) = T(n-1) + T(n-2) + 1 ; T(0) = 0, T(1) = 1

T(2) = 1 + T(1) + T(0) = 1 + 1 + 0 = 2

T(3) = 1 + T(2) + T(1) = 1 + 2 + 1 = 4

…..

T(10) = 1 + T(9) + T(8) = 143