GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
265 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 Junior (513 points)  
edited by | 265 views

2 Answers

+4 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 (53.3k 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 (681 points)  


Top Users Aug 2017
  1. Bikram

    5034 Points

  2. ABKUNDAN

    4730 Points

  3. akash.dinkar12

    3488 Points

  4. manu00x

    3296 Points

  5. rahul sharma 5

    3178 Points

  6. makhdoom ghaya

    2530 Points

  7. just_bhavana

    2428 Points

  8. stblue

    2240 Points

  9. Tesla!

    2076 Points

  10. joshi_nitish

    1830 Points


25,032 questions
32,178 answers
74,993 comments
30,218 users