GATE CSE 2011 | Question: 32

Question

Consider a database table T containing two columns $\text{X}$ and $\text{Y}$ each of type $\text{integer}$. After the creation of the table, one record $\text{(X=1, Y=1)}$ is inserted in the table.

Let $\text{MX}$ and $\text{MY}$ denote the respective maximum values of $\text{X}$ and $\text{Y}$ among all records in the table at any point in time. Using $\text{MX}$ and $\text{MY}$, new records are inserted in the table $128$ times with $\text{X}$ and $\text{Y}$ values being $\text{MX+1, 2*MY+1}$ respectively. It may be noted that each time after the insertion, values of $\text{MX}$ and $\text{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. $255$
• C. $129$
• D. $257$

Comments

Detailed Video Solution, with Complete Analysis & Variations: https://youtu.be/zb6vXpZVo1E?t=4186&feature=shared

Assume $n$ new tuples are inserted, & If query asks $sum(X), sum(Y)$, then:

$Sum(X) = (n+1)(n+2)/2$

$Sum(Y) = 2(2^{n+1}-1) - (n+1)$

---

Simulate acc. to question

Answer 1

$X = 1, Y = 1$

$X = 2, Y = 2\times 1 +1 = 3$

$X = 3, Y = 2\times 3 + 1 = 7$

$X = 4, Y = 2\times 7 + 1 = 15$

$X = 5, Y = 2\times 15 + 1 = 31$

$X = 6, Y = 2\times 31+1 = 63$

$X = 7, Y = 2\times 63 + 1 = 127$

Correct Answer: $A$

Comments

@jeet sir, thanks for response. I assume yes is for the first query.

 

regarding the 2nd query, is there any usefulness or significance of "records inserted in table 128 times"

---

I think it's just a number. Don't have and such significance.

---

@Mayank0343 @`JEET

Yes, the number 128 has significance. It tells after X=Y=1, we have to insert 128 times the value of X and Y according to the given formula.

If the question were:

SELECT Y FROM T WHERE X=129;

It would have given an error.

Answer 2

OPTION A is the answer

if you do this as mentioned by Arjun sir then you will get the answer 

$X = 1, Y = 1$

$X = 2, Y = 2*1 +1 = 3$

$X = 3, Y = 2*3 + 1 = 7$

$X = 4, Y = 2*7 + 1 = 15$

$X = 5, Y = 2*15 + 1 = 31$

$X = 6, Y = 2*31+1 = 63$

$X = 7, Y = 2*63 + 1 = 127$

but if this question will be extended to $X=$ $'N'$ value then if you observe the pattern then it will come out as

$Y=2^{N}-1$ and here it is asked for $X=7$ so if we put $X$ value then we will get $(2^{7}- 1= 128-1=127)$

Suppose if they asked for $X=128$ then $Y=2^{128}-1$ is the answer.

Comments

Not sure if this is being monitored. But can you please explain how you are deriving the relation between Mx and My ?

---

when $MX=1$ , $MY=1$ (only 1 term which is equal to the value of $MX$)

when $MX=2$ , $MY=1 + 2$ (total 2 terms which is equal to the value of $MX$)

when $MX=3$ , $MY=1 + 2 + 2^{2}$ (total 3 terms which is equal to the value of $MX$)

when $MX=4$ , $MY=1 + 2 + 2^{2} + 2^{3}$ (total 4 terms which is equal to the value of $MX$)

............

Similarly ,

when $MX=n$ , $MY=1 + 2 + 2^{2} + 2^{3}+......+2^{n-1}$ (total $n$ terms which is equal to the value of $MX$)

So, for $MX=n$ ,

$MY=1 + 2 + 2^{2} + 2^{3}+......+2^{n-1}$ = $2^{n}-1$

Answer 3

MY is simply doing the shift of the previous number in binary to left and adding 1 in LSB. So, after 6 additions to table, MX will be 7 and there will be seven 1's in MY which is equivalent to 2^8-1 in decimal.

Answer 4

After inserting 4 values we can interpret that its forming a series were elements next to it are found by adding powers of 2.

Interpreting it as a series is helpful because if the query would ask for any value of x greater than 10 then individual substitution will be time consuming. 

See the solution below for more understanding 

Hence option A is Answer (i.e 127) 

Answer 5

1       1

1+1  2+1

2+1  2(3)+1

3+1  2(7)+1

4+1  2(15)+1

5+1   2(31)+1

6+1  2(63)+1

so for x=7 y will be 127

Answer 6

X	Y
1	1
2	3
3	7

When X=3 is inserted, it is 2nd new record after X=1.

Just look at corresponding Y value; 7 = 2^0 + 2^1 + 2^2

 

So, when X=7 is inserted, it is 6th new record. 

Y = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6

      

Sum of n terms of GP = a * (r^n - 1) / (r - 1)

Here, a = 2, n =7

 

Therefore, S_n = 1 * (2^7 - 1) / (2 - 1)

                         = 2^7 - 1

                         = 127