# Answer to Question #9072 in C++ for tanisly

Question #9072

write using c.In a disordered array of k(m) is the matching items from each group of identical items will leave only one remaining, and removing pursing an array to the beginning

Expert's answer

int findKthSmallest(int A[], int m, int B[], int n, int k) {

& assert(m >= 0); assert(n >= 0); assert(k > 0); assert(k <= m+n);

& int i = (int)((double)m / (m+n) * (k-1));

& int j = (k-1) - i;

& assert(i >= 0); assert(j >= 0); assert(i <= m); assert(j <= n);

& // invariant: i + j = k-1

& // Note: A[-1] = -INF and A[m] = +INF to maintain invariant

& int Ai_1 = ((i == 0) ? INT_MIN : A[i-1]);

& int Bj_1 = ((j == 0) ? INT_MIN : B[j-1]);

& int Ai = ((i == m) ? INT_MAX : A[i]);

& int Bj = ((j == n) ? INT_MAX : B[j]);

& if (Bj_1 < Ai && Ai < Bj)

return Ai;

& else if (Ai_1 < Bj && Bj < Ai)

return Bj;

& assert((Ai > Bj && Ai_1 > Bj) ||

(Ai < Bj && Ai < Bj_1));

& // if none of the cases above, then it is either:

& if (Ai < Bj)

// exclude Ai and below portion

// exclude Bj and above portion

return findKthSmallest(A+i+1, m-i-1, B, j, k-i-1);

& else /* Bj < Ai */

// exclude Ai and above portion

// exclude Bj and below portion

return findKthSmallest(A, i, B+j+1, n-j-1, k-j-1);

}

& assert(m >= 0); assert(n >= 0); assert(k > 0); assert(k <= m+n);

& int i = (int)((double)m / (m+n) * (k-1));

& int j = (k-1) - i;

& assert(i >= 0); assert(j >= 0); assert(i <= m); assert(j <= n);

& // invariant: i + j = k-1

& // Note: A[-1] = -INF and A[m] = +INF to maintain invariant

& int Ai_1 = ((i == 0) ? INT_MIN : A[i-1]);

& int Bj_1 = ((j == 0) ? INT_MIN : B[j-1]);

& int Ai = ((i == m) ? INT_MAX : A[i]);

& int Bj = ((j == n) ? INT_MAX : B[j]);

& if (Bj_1 < Ai && Ai < Bj)

return Ai;

& else if (Ai_1 < Bj && Bj < Ai)

return Bj;

& assert((Ai > Bj && Ai_1 > Bj) ||

(Ai < Bj && Ai < Bj_1));

& // if none of the cases above, then it is either:

& if (Ai < Bj)

// exclude Ai and below portion

// exclude Bj and above portion

return findKthSmallest(A+i+1, m-i-1, B, j, k-i-1);

& else /* Bj < Ai */

// exclude Ai and above portion

// exclude Bj and below portion

return findKthSmallest(A, i, B+j+1, n-j-1, k-j-1);

}

Need a fast expert's response?

Submit orderand get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

## Comments

## Leave a comment