GATE CS 2024 Set 1 | Question 48

MSQ · 2 marks

Consider the following C function definition.

int f(int x, int y) {
  for (int i=0; i<y; i++) {
    x=x+x+y;
  }
  return x;
}

Which of the following statements is/are TRUE about the above function?

  1. Option A: If the inputs are x=20, y=10, then the return value is greater than \(2^{20}\)
  2. Option B: If the inputs are x=20, y=20, then the return value is greater than \(2^{20}\) (correct)
  3. Option C: If the inputs are x=20, y=10, then the return value is less than \(2^{10}\)
  4. Option D: If the inputs are x=10, y=20, then the return value is greater than \(2^{20}\) (correct)

Answer

(B), (D)

Explanation

Each iteration sets \(x \leftarrow 2x + y\), and the loop runs \(y\) times. Adding \(y\) to both sides shows that \(x + y\) doubles on every iteration, so the function returns \(2^{y}(x + y) - y\).

  • x=20, y=10: \(2^{10} \cdot 30 - 10 = 30710\). That is below \(2^{20} = 1048576\) but above \(2^{10} = 1024\), so A and C are false.
  • x=20, y=20: \(2^{20} \cdot 40 - 20 = 41943020 \gt 2^{20}\), so B is true.
  • x=10, y=20: \(2^{20} \cdot 30 - 20 = 31457260 \gt 2^{20}\), so D is true.

Both large results are below \(2^{31} - 1\), so int does not overflow.

Answer: B, D