GATE IT 2005 | Question: 59

Question

Let $a$ and $b$ be two sorted arrays containing $n$ integers each, in non-decreasing order. Let $c$ be a sorted array containing $2n$ integers obtained by merging the two arrays $a$ and $b$. Assuming the arrays are indexed starting from $0$, consider the following four statements

1. $a[i] \geq b [i] \Rightarrow c[2i] \geq a [i]$
2. $a[i] \geq b [i] \Rightarrow c[2i] \geq b [i]$
3. $a[i] \geq b [i] \Rightarrow c[2i] \leq a [i]$
4. $a[i] \geq b [i] \Rightarrow c[2i] \leq b [i]$

Which of the following is TRUE?

• A. only I and II
• B. only I and IV
• C. only II and III
• D. only III and IV

Comments

A small thing to be noticed :

"=>" i.e implication is mentioned in question.

that means, condition given in LHS of option must hold true first then only we can claim for RHS.

If LHS is not satisfied then its irrelevant to check RHS.

---

A= [50,70,80]

B=[10,20,70]

Can anybody pls explain using this example array.

---

@Ekta07_GATE

$a=[50, 70, 80]$ $b=[10, 20, 70]$

$\therefore$ $c=[10, 20, 50, 70, 70, 80]$ 

Lets take a[2] & b[2]: $a[2]>=b[2]$ and therefore $c[4]>=b[2]$ and $c[4]<=a[2]$

Similarly you can check for other positions. Only II and III condition holds for all positions.

Answer 1

$a[i] \geq b[i]$

Since both $a$ and $b$ are sorted in the beginning, there are $i$ elements smaller than or equal to $a[i] (i$ starts from $0)$, and similarly $i$ elements smaller than or equal to $b[i]$. So, $a[i] \geq b[i]$ means there are $2i$ elements smaller than or equal to $a[i]$, and hence in the merged array $a[i]$ will come after these $2i$ elements (its index will be $> 2i$). So, $c[2i] \leq a[i]$ (equality takes care of the "equal to" case which comes when array contains repeated elements).

Similarly, $a[i] \geq b[i]$ says for $b$ that, there are not more than $2i$ elements smaller than $b[i]$ in the sorted array ($i$ elements from $b$, and maximum another $i$ elements from $a$). So, $b[i] \leq c[2i]$

So, II and III are correct.

Option (C).

Comments

@jatinmittal199510

Yes, it should be 2i+1 because b[i] is involved too.

---

It’s not just this example. Even the example I took, I ended up having IV as true, same thing as yours.

Although, I is definitely not true and II is definitely true. So that leaves us with just option C. If one is solving using examples, that’s the way to go. Because everyone would be considering different examples!   

I’m not sure if the question was meant to be solved that way (i.e. by eliminating options). But the method provided by Arjun sir is pretty robust.

---

What an answer sir, bravo!!!

Answer 2

Take One example which satisfy given constraint in question.

A= {40,50,60}

B={10,20,30}

Both Array have n elements and they are in non-decreasing order(they may contain equal no.s in asc. order)

C={10,20,30,40,50,60}

Array index starts with 0.

Now take i=2

A[2] >= B[2]

So now check all options

I. C[4]  >= A[2].  50 >= 60 . False

II.C[4] >= B[2].   50>= 30 . True

III.C[4] <= A[2].   50<=60.  True

IV. C[4] <= B[2].   50 <=30.  False

So Option C is Correct Ans.

Comments

smart thinking ....

---

Nice explanation sir. Thank you soooo much.

---

Always Examples Make Things Easy !

Answer 3

Arrays : a,b have “n” elements .

c  has “2n” elements.

 

If a[i] >=b[i]; that says us that the a[i] ^th element would appear minimum at 2i+1 index or max at i+n index . (if a[i-1] ==a[i] then this value can be present at 2i too)

and the b[i]^th element would appear minimum at i+1 index or max at 2i index

Keep these 2 facts in mind, and lets read the options : 

1. c[2i]  >= a[i] ; c[2i] =a[i] can happen when a[i-1] ^th value has got placed at 2i, but as a[i]^th will be placed minimum at 2i+1, all the elements before it would be either less than or equal to it, meaning, c[2i] will be always <= a[i], thus this option is wrong and this makes option 3 right.
2. c[2i] >=b[i] ; b[i]^th element will be minimum placed at i+1 : this means the c[2i] is definately >= b[i] , and b[i] could be placed at 2i max, in case where still the equation holds true due to equality, this means that, at c[2i], there can never be a value less than b[i], but always will be a value >= b[i]. This makes this option true and 4^th option false.
3. Explained in 1
4. Explained in 2

Thus, 2^nd and 3^rd options are right. Thus, option C : only II and III

 

I hope this helps, you may also do this with example, but this proof way eliminates all doubts in mind.

Answer 4

Option C is correct answer ,

here is the counter example for other options – 

lets take A[]={1,2,5,6} , B[]= {3,4,4,4}

now lets check for i=2 (index starting from 0 so a[i]=5) ,

by this example ,you can check that only option C implication is valid .