GATE CSE
First time here? Checkout the FAQ!
x
0 votes
178 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 | 178 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.2k 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 (641 points)  
Top Users Jan 2017
  1. Debashish Deka

    7906 Points

  2. Habibkhan

    4736 Points

  3. Vijay Thakur

    4474 Points

  4. sudsho

    4318 Points

  5. saurabh rai

    4200 Points

  6. Arjun

    3638 Points

  7. Bikram

    3500 Points

  8. santhoshdevulapally

    3470 Points

  9. GateSet

    3228 Points

  10. Sushant Gokhale

    3116 Points

Monthly Topper: Rs. 500 gift card

18,944 questions
23,897 answers
52,119 comments
20,213 users