retagged by
13,007 views
35 votes
35 votes

Consider the following program written in pseudo-code. Assume that $x$ and $y$ are integers.

Count (x, y) {
    if (y !=1 ) {
        if (x !=1) {
            print("*");
            Count (x/2, y);
        }
        else {
            y=y-1;
            Count (1024, y);
        }
    }
}

The number of times that the $print$ statement is executed by the call $Count(1024, 1024)$ is _____

retagged by

7 Answers

Best answer
37 votes
37 votes
Count (x, y) {
    if (y !=1 ) {
        if (x !=1) {
            print("*");
            Count (x/2, y);
        }
        else {
            y=y-1;
            Count (1024, y);
        }
    }
}

Here, for each y value print("$*$") will run $10$ times. Once $x$ value reaches $1$, $count(1024, y-1)$ will be called. Variable $y$ can take values $[2\ \ 1024]$ $i.e.$ total $1023$ values. So,

The total number of times '$*$' will be printed =  $\big($Number of times '$*$' printed per $y$ value$\big)$*$\big($number of values $y$ takes$\big)$.

Number of times '$*$' printed $= 10* 1023 = 10230$

edited by
26 votes
26 votes
The very first time when count(1024,1024) is called, then the print("*") will be executed 10 times until "x" becomes 1.

When "x" becomes 1,the "else" condition will be executed thereafter, hence it will execute 1022 times followed by if-condition(until "y" becomes 1)

So,

No of times print("*") will execute = 10 + 1022*10 = 10230
10 votes
10 votes

count(1024,1024) → count(512,1024) → count(256,1024) → count(128,1024) → count(64,1024) → count(32,1024) → count(16,1024) → count(8,1024) → count(4,1024) → count(2,1024) → count(1,1024)

 

Now, x = 1, so go to the else part. Print WON'T be accessed in this go. 

Total prints till now = 10.

 

Now, count(1024, 1023): 10 more prints.

count(1024, 1022): 10 more prints.

count(1024, 1021): 10 more prints.

...

...

count(1024,1): y = 1, so if/else body won't be accessed. No prints.

 

Hence, for 1023 times, we access the print statement for 10 different values of x.

=> 1023 * 10 prints

=> 10230.

5 votes
5 votes

Instead of print, simulated with a global count variable.

Ans: 10230

Answer:

Related questions

23 votes
23 votes
5 answers
1
38 votes
38 votes
5 answers
2
gatecse asked Feb 14, 2018
21,946 views
Consider the weights and values of items listed below. Note that there is only one unit of each item.$$\begin{array}{|c|c|c|}\hline \textbf{Item number} & \textbf{Weigh...
35 votes
35 votes
9 answers
3
gatecse asked Feb 14, 2018
17,354 views
Consider the following undirected graph $G$:Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $...