GATE CSE
First time here? Checkout the FAQ!
x
0 votes
243 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 | 243 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 (53k 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 Jun 2017
  1. Bikram

    3912 Points

  2. Arnab Bhadra

    1526 Points

  3. Hemant Parihar

    1502 Points

  4. Niraj Singh 2

    1491 Points

  5. Debashish Deka

    1450 Points

  6. junaid ahmad

    1432 Points

  7. pawan kumarln

    1278 Points

  8. Rupendra Choudhary

    1242 Points

  9. rahul sharma 5

    1240 Points

  10. Arjun

    1228 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 26 - Jul 02
  1. pawan kumarln

    410 Points

  2. akankshadewangan24

    334 Points

  3. Arjun

    268 Points

  4. Abhisek Das

    230 Points

  5. Bikram

    208 Points


23,433 questions
30,147 answers
67,595 comments
28,476 users