"=>" 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.

Dark Mode

9,478 views

49 votes

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

- $a[i] \geq b [i] \Rightarrow c[2i] \geq a [i]$
- $a[i] \geq b [i] \Rightarrow c[2i] \geq b [i]$
- $a[i] \geq b [i] \Rightarrow c[2i] \leq a [i]$
- $a[i] \geq b [i] \Rightarrow c[2i] \leq b [i]$

Which of the following is TRUE?

- only I and II
- only I and IV
- only II and III
- only III and IV

53 votes

Best answer

$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**).

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.

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.

0

69 votes

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.

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.

0 votes

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 :

- 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. - 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. - Explained in 1
- 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.