Problem: You are given three sorted arrays A, B, and C each having n numbers. You can assume that you can compare two elements from A∪B∪C in O(1)-time. Let k be an integer. Design an algorithm that outputs the k-th smallest element of A∪B∪C. The running time of your algorithm must be faster than O(n). Try to optimize the running time of your algorithm as much as possible.
N.B. If your algorithm runs in O(n)-time, then you will receive at most 10% credit.
1
