3.8k views

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 _____

edited | 3.8k views
+1
$10230$?
+1
I got 1032 as well. But somewhere people were getting 10320.
+1
10230
+4
1,1 = 'if' condition fails thus print doesn't execute at all.

2,2 = 1*1 = 1

4,4 = 3*2 = 6

8,8 = 7*3 = 21

16,16 = 15*4 = 60

32,32 = 31*5 = 155

64,64 = 63*6 = 378

.

.

.

1024,1024 = 1023 * 10  = 10230

Start analyzing with small similar values.
+1
@Tuhin Dutta

I do not understand 1,1 = 0*0 =0

+1
now it should be clear
+1
why you do multiplication??
+1
Outer recursion or loop * Inner recursion or loop

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$

by Veteran (60.9k points)
edited
+1
How 10230.. it would be 10.. y will just decrements and returns.. so print f will be executed 10 times I think.
0
what is the intital values of x and y
0
Initial values are given in question itself...
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
by Active (2.1k points)
+1
@kaurbaljit can u plz explain the last step of your solution
+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!
+1
@baljitkaur and u added 10 there to get the final result..why u add that 10?
+2
Its for the first time when count(1024,1024) is called,where the if-condition will execute log base2 1024 times i.e, "10"(until x becomes 1).

Thereafter, when "x" becomes 1 then control will be directed to the else statement followed by the inner-if for each value of "y".
+1
okay thanku so much @baljit kaur Instead of print, simulated with a global count variable.

Ans: 10230

by Active (1.3k points)
+1
Yes You are correct answer is 10230

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$.

by Active (3.5k points)
edited
+1

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.

by Loyal (6.5k points)
+1 vote

$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$

by Active (4.1k points)
edited