The Gateway to Computer Science Excellence
+15 votes
3.5k 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 _____

in Programming by Boss (16.8k points)
edited by | 3.5k 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

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

5 Answers

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

by Veteran (60.5k points)
edited by
+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...
+11 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
by Active (2k 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
+5 votes

Instead of print, simulated with a global count variable.

Ans: 10230

by Active (1.3k points)
+1
Yes You are correct answer is 10230
+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$.
 

by Active (3.2k points)
edited by
+1
Excellent answer.
+1 vote

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 Active (2.2k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,644 questions
56,505 answers
195,555 comments
101,046 users