GATE 2024 CS1 Q.48: solution and answer

GATE 2024 · CS1Q.48 · 2 marks · MSQ

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?

(A)
If the inputs are x=20, y=10, then the return value is greater than $2^{20}$
(B)
If the inputs are x=20, y=20, then the return value is greater than $2^{20}$
(C)
If the inputs are x=20, y=10, then the return value is less than $2^{10}$
(D)
If the inputs are x=10, y=20, then the return value is greater than $2^{20}$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Statements (B) and (D) are TRUE; the correct answer is (B) and (D).

Official answer: B, DSource: Official answer key, GATE 2024 CS1 (IISc Bengaluru)

The for (int i=0; i<y; i++) loop executes exactly $y$ times (i = 0 to y−1), and each iteration performs x=x+x+y, i.e. $x \leftarrow 2 x + y$ .
This defines the linear recurrence $x_{n + 1} = 2 x_{n} + y$ with $x_{0} = x$ (the input value of x).
Solving by unrolling/induction: $x_{1} = 2 x_{0} + y$ , $x_{2} = 4 x_{0} + 3 y$ , and in general $x_{n} = 2^{n} x_{0} + y (2^{n} - 1)$ .
So the value returned after the loop (n = y iterations) is $x_{y} = 2^{y} x_{0} + y (2^{y} - 1) .$
(A) x=20, y=10: $x_{10} = 2^{10} (20) + 10 (2^{10} - 1) = 20480 + 10230 = 30710$ . Since $2^{20} = 1, 048, 576$ and $30710 < 2^{20}$ , statement (A) is FALSE.
(B) x=20, y=20: $x_{20} = 2^{20} (20) + 20 (2^{20} - 1) = 20, 971, 520 + 20, 971, 500 = 41, 943, 020$ , which is greater than $2^{20} = 1, 048, 576$ . Statement (B) is TRUE.
(C) x=20, y=10: $x_{10} = 30710$ (from step 5), and $2^{10} = 1024$ . Since $30710 > 1024$ , the claim 'less than $2^{10}$ ' is FALSE.
(D) x=10, y=20: $x_{20} = 2^{20} (10) + 20 (2^{20} - 1) = 10, 485, 760 + 20, 971, 500 = 31, 457, 260$ , which is greater than $2^{20} = 1, 048, 576$ . Statement (D) is TRUE.
Only (B) and (D) are TRUE.

KEY IDEA

The loop runs exactly $y$ times, and each iteration replaces x by x=x+x+y, i.e. the linear recurrence $x_{n + 1} = 2 x_{n} + y$ . Unrolling this recurrence gives a closed form $x_{n} = 2^{n} x_{0} + y (2^{n} - 1)$ , which lets every option be checked by a single arithmetic comparison instead of by re-running the loop by hand.

WATCH OUT FOR

Reading x=x+x+y as x = 2x and forgetting the +y term each iteration (or, symmetrically, treating the recurrence as $x_{n + 1} = 2 (x_{n} + y)$ instead of $2 x_{n} + y$ ), which changes the growth rate and can flip (D) to false when it is actually true; also common is comparing the final value to $2^{y}$ instead of the specific power asked for in each option (e.g. checking against $2^{10}$ for option A instead of $2^{20}$ ).

From the GATE 2024 CS1 paper. Every question of this paper · Download the full paper · All 7 C basics questions, with notes

GATE 2024 CS1 Q.48: solution and answer

Answer and solution

More C basics questions