GATE CSE 2018 | Question: 45

Question

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 _____

Comments

$10230$?

---

I got 1032 as well. But somewhere people were getting 10320.

---

10230

---

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.

---

@Tuhin Dutta

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

please explain more clear

---

now it should be clear

---

why you do multiplication??

---

Outer recursion or loop * Inner recursion or loop

---

from the first call count(1024 1024) both if conditions are satisfied and therefore it execuetes printf statemnt 10 times becuse

1024=2^10

so for y=1024 it executes printf statement 10 times

y values\ is decremented by 1 in each iteration

y decrements from 1024 to 1 and when it reaches one the condition terminates so 1024-1=1023 times it calls count

therefore total no of times eintf gets executed is 1023*10=10230.

i hope you got this thankyou

---

for this kind of iteration we need to take small values and check.

Answer 1

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$

Comments

2^10 = 1024

---

Awesome bhai

---

To all who are confused in counting the range

https://brilliant.org/wiki/counting-integers-in-a-range/

Answer 2

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

Comments

@baljitkaur and u added 10 there to get the final result..why u add that 10?

---

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

---

okay thanku so much @baljit kaur

Answer 3

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.

Answer 4

Instead of print, simulated with a global count variable.

Ans: 10230

Comments

Yes You are correct answer is 10230