The Gateway to Computer Science Excellence

+18 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 _____

+19 votes

Best answer

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$

+18 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

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

+1

When x becomes 1,then inner if-condition becomes false and the control will be transferred to else statement,so y becomes 1023 ,and count function will be called ,so for each value of "y" the print statement will be executed 10 times,hence 1022*10 times(until y=1).

Hope you get it!

Hope you get it!

+5 votes

+2 votes

Look at the function. It's recursive. We write it mathematically as stated below.

$\mathrm{Count}(x,y)= \left\{\begin{matrix} \emptyset & y= 1\\ \mathrm{Count}(\lfloor \frac{x}{2}\rfloor,y) & x\ne 1, y\ne 1 \\ \mathrm{Count}(1024,y-1) & x=1, y\ne 1 \end{matrix}\right.$

It means the first parameter $x$ is being halved by every call until $x=1$. In fact, the first parameter $x$ is decreased geometrically (logarithmically **based 2**) like $(1024,512,256,...,1)$. On the other hand, the second parameter $y$ is linearly decreasing by 1 until $y=1$ like $(1024,1023,1022,...,1)$.

So **roughly** the number of times $\mathrm{Count}(x,y)$ being called $=O(\log_{2}(x)+y)$. More accurately it is $\log_{2}x +\log_{2}(1024) \times (y-2)$

$\therefore$ The number of times $\mathrm{Count}(1024,1024)$ being called is $$\begin{align}\log_{2}(1024) +\log_{2}(1024) \times (1024-2)&={\log_{2}(1024)}\times(1024-1)\\&=10\times 1023=10230 \end{align}$$

So the correct answer is $10230$.

+2 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.

+2 votes

$C(1024,1024)$$\rightarrow*$

$\downarrow$

$C(512,1024)\rightarrow*$

$\downarrow$

$C(256,1024)\rightarrow*$

$\downarrow$

$C(128,1024)\rightarrow*$

$\downarrow$

$C(64,1024)\rightarrow*$

$\downarrow$

$C(32,1024)\rightarrow*$

$\downarrow$

$C(16,1024)\rightarrow*$

$\downarrow$

$C(8,1024)\rightarrow*$

$\downarrow$

$C(4,1024)\rightarrow*$

$\downarrow$

$C(2,1024)\rightarrow*$

$\downarrow$

$C(1,1024)$

$\downarrow$

$C(1024,1023)$

Similary for $C(1024,1023)=10\ stars$ & so on until $C(1024,2)=10\ stars$

$For\ C(1024,1)$ Program terminates

$\therefore$ It runs 1023 times & each time 10 stars generated leading to $1023\times 10=10230\ stars$

52,375 questions

60,574 answers

201,979 comments

95,389 users