edited by
11,672 views
56 votes
56 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

  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?

  1. only I and II
  2. only I and IV
  3. only II and III
  4. only III and IV
edited by

5 Answers

Best answer
56 votes
56 votes

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

edited by
71 votes
71 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.
0 votes
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 : 

  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 4th option false.
  3. Explained in 1
  4. Explained in 2

Thus, 2nd and 3rd 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.

0 votes
0 votes

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 .

 

 

Answer:

Related questions

25 votes
25 votes
3 answers
3
Ishrat Jahan asked Nov 3, 2014
8,917 views
What is the output printed by the following program?#include <stdio.h int f(int n, int k) { if (n == 0) return 0; else if (n % 2) return f(n/2, 2*k) + k; else return f(n/...