GATE CSE
First time here? Checkout the FAQ!
x
0 votes
222 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 | 222 views

2 Answers

+3 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.7k 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 (669 points)  


Top Users Apr 2017
  1. akash.dinkar12

    3826 Points

  2. Divya Bharti

    2796 Points

  3. Deepthi_ts

    2294 Points

  4. rude

    2142 Points

  5. Prashant.

    1900 Points

  6. Tesla!

    1888 Points

  7. Kapil

    1842 Points

  8. Debashish Deka

    1830 Points

  9. Arjun

    1810 Points

  10. Sanjay Sharma

    1712 Points

Monthly Topper: Rs. 500 gift card

22,177 questions
28,200 answers
63,649 comments
24,364 users