GATE CSE
First time here? Checkout the FAQ!
x
0 votes
192 views

How many asterisks $(*)$ in terms of $k$ will be printed by the following C function, when called as $\text{count}(m)$ where $m = 3^k$ ? Justify your answer.

Assume that $4$ bytes are used to store an integer in C and $k$ is such that $3^k$ can be stored in $4$ bytes.

void count(int n){
    printf("*");
    
    if(n>1){
        count(n/3);
        count(n/3);
        count(n/3);
    }
}
asked in Programming by (483 points)  
edited by | 192 views

2 Answers

+2 votes
Best answer

I tried it for 35 ,

in every call it print "*" one time 

and each function call 3 functions for n/3 recursively till get 1 at each node . it becomes a ternary tree 

call for 35 -----------------------1 = 30 

call for 34 -----------------------3 = 31

call for 33  ---------------------9 = 32

call for 32  --------------------27 =33 

call for 31 ---------------------81 = 34 

call for 30 --------------------243 = 35

so one "*" print at each function call 

no of "*" printed = 30 +31 +32 +......3k  [ that makes GP series ] 

 = 1 * (1 - 3k+1)/(1-3)

 = (3k+1 -1 )/2 

[ Note : I am not sure about it , feel free for edit ] 

answered by Veteran (52.4k points)  
selected by
0 votes

T(3k) = 3T(3k-1)+1, This is the recurrence relation of the above program. +1 is number of times *is printed, so during 1st call 1 * will be printed.

T(3k) = 3T(3k-1) + 1

         = 32(T(3k-2) + 3 + 1

          = 33(T(3k-3) + 9 + 3 + 1.....

          continue upto k-1

1 + 3 + 32 + ..... 3k-1= 1(1- 3k-1)/1-3

 

 

answered by Junior (659 points)  
Top Users Feb 2017
  1. Arjun

    4898 Points

  2. Bikram

    4102 Points

  3. Habibkhan

    3748 Points

  4. Aboveallplayer

    2986 Points

  5. sriv_shubham

    2288 Points

  6. Smriti012

    2222 Points

  7. Arnabi

    1946 Points

  8. Debashish Deka

    1920 Points

  9. mcjoshi

    1614 Points

  10. sh!va

    1462 Points

Monthly Topper: Rs. 500 gift card

20,793 questions
25,951 answers
59,557 comments
21,976 users