ISRO CS 2023 Q.30: solution and answer

ISRO 2023 · CSQ.30 · 1 mark · MCQ

Consider a database table T containing two columns X and Y each of type Integer. After the creation of the table, one record (X=1, Y=1) is inserted in the table. Let MX and MY denote the respective maximum values of X and Y among all records in the table at any point in time. Using MX and MY, new records are inserted in the table 128 times with X and Y values being MX+1, 2 × MY+1 respectively. It may be noted that each time after the insertion, values of MX and MY change. What will be the output of the following SQL query after the steps mentioned above are carried out?

SELECT Y FROM T WHERE X=7;

(A)
127
(B)
15
(C)
129
(D)
257

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The query returns 127, option (A).

Official answer: ASource: ISRO's revised and final answer key of 16 February 2024

The table starts with one row $(X, Y) = (1, 1)$ . Each new row uses the current maxima: $X_{new} = M X + 1$ and $Y_{new} = 2 \times M Y + 1$ .
Every new row has larger $X$ and $Y$ than all earlier rows, so the newest row always holds both maxima. Hence the next row is computed from the previous row alone.
Let $(X_{k}, Y_{k})$ be the row added by insertion $k$ , with $(X_{0}, Y_{0}) = (1, 1)$ . Then $X_{k} = X_{k - 1} + 1$ , so $X_{k} = k + 1$ .
Also $Y_{k} = 2 Y_{k - 1} + 1$ . Adding 1 to both sides gives $Y_{k} + 1 = 2 (Y_{k - 1} + 1)$ , with $Y_{0} + 1 = 2$ . So $Y_{k} + 1 = 2^{k + 1}$ and $Y_{k} = 2^{k + 1} - 1$ .
The query asks for $X = 7$ , so $k + 1 = 7$ and $k = 6$ . This is within the 128 insertions, and since $X$ strictly increases, $X = 7$ occurs in exactly one row.
Then $Y_{6} = 2^{7} - 1 = 127$ . Check by repeated doubling plus one: $1, 3, 7, 15, 31, 63, 127$ . The sixth insertion gives $127$ , and the query returns this single value.

KEY IDEA

Each new row is built from the current maxima, which always belong to the latest row. So the $Y$ values follow $Y_{k} = 2 Y_{k - 1} + 1$ , giving $Y_{k} = 2^{k + 1} - 1$ , while $X_{k} = k + 1$ .

WATCH OUT FOR

Being off by one in the index: the row with $X = 7$ is the sixth inserted row, not the seventh, because the starting row already has $X = 1$ . Using the wrong index gives 63 or 255 instead of 127. Option (B) 15 is the $Y$ value for $X = 4$ .

From the ISRO CS 2023 paper. Every question of this paper · The full paper (PDF, ISRO) · All 4 ISRO SQL questions, with notes

ISRO CS 2023 Q.30: solution and answer

Answer and solution

More ISRO SQL questions