The Gateway to Computer Science Excellence
+27 votes

Consider the following C-function in which $a[n]$ and $b[m]$ are two sorted integer arrays and $c[n+m]$ be another integer array,

void xyz(int a[], int b [], int c []){ 
    int i,j,k; 
    while ((i<n) && (j<m)) 
        if (a[i] < b[j]) c[k++] = a[i++]; 
        else c[k++] = b[j++]; 

Which of the following condition(s) hold(s) after the termination of the while loop?

  1. $j< m,k=n+j-1$ and $a[n-1]< b[j]$ if $i=n$
  2. $i<n,k=m+i-1$ and $b[m-1]\leq a[i]$ if $j=m$
  1. only (i) 
  2. only (ii) 
  3. either (i) or (ii) but not both 
  4. neither (i) nor (ii) 
in Algorithms by
edited by | 4.9k views

3 Answers

+64 votes
Best answer

The while loop adds elements from $a$ and $b$ (whichever is smaller) to $c$ and terminates when either of them exhausts. So, when loop terminates either $i = n$ or $j = m$. 

Suppose $i = n$. This would mean all elements from array $a$ are added to $c => k$ must be incremented by $n$. $c$ would also contain $j$ elements from array $b$. So, number of elements in $c$ would be $n+j$ and hence $k = n + j$. 

Similarly, when $j = m$, $k = m + i$. 

Hence, option (D) is correct. (Had $k$ started from $-1$ and not $0$ and we used $++k$ inside loop, answer would have been option (C))

edited by

Small correction

Similarly, when j = m, k = n + i. 

Change n to m.

Thanks :)
@arjun sir . if we take same element in same index of both array . we can come to solution directly.

i took A[ 12 3] and B [1259] :).

Its very hard  for me to interpret the code by seeing :(
@arjun sir,

1) K1=K1++ or 2)K1=++K1

here in 1, 2 cases K value is different  but

generally just increment operation without assigning to any value will be same in both pre increment and post increment.

K++,   ++k


Am i wrong?

@Yashaswini Vanaja           yes in loops both are same 

I understood like this - For $(i):$ $k$ is incremented after fillling $c$. So at the end of loop $k$ increments after filling $n-1 + j$ values which is $n+j$.
+28 votes
By Option Elimination

Take Array Contents

a={1} b={2} so n=1,m=1

Now A is small so it will copy to C then terminate in next iteration cz i<n no more holds So content of variables after while loop

c={1} , i=1,j=0,k=1,n=1,m=1

Check Condition i :->> (i==n) Yes. j<m holds but k=n+j-1 does not hold ,So Condition i is false.


Now Take Array Contents

a={2} b={1} so n=1,m=1

Now B is small so it will copy to C then terminate in next iteration cz j<m no more holds So content of variables after while loop

c={1} , i=0,j=1,k=1,n=1,m=1

Check Condition ii :->> (j==m) Yes. i<n holds but k=m+i-1 does not hold ,So Condition ii is false.

 Neither condition holds Hence Option D is correct Ans.
edited by
thanks, good example :)
+8 votes

Option A and B are incorrect because j<m or i<n for loop termination.

From remaining C and D , k is no of elements added in c. it would either be n+j or m+i after loop terminates not n+j-1...

So D should be the correct answer


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,375 questions
60,580 answers
95,396 users