Search code examples
algorithmdivide-and-conquer

Finding the k smallest odd integer

Actually, I am teaching myself algorithm and here I am trying to solve this problem which is the following:

We have an array of n positive integers in an arbitrary order and we have k which is k>=1 to n. The question is to output k smallest odd integers. If the number of odd integers in A is less than k, we should report all odd integers. For example, if A = [2, 17, 3, 10, 28, 5, 9, 4, 12,13, 7] and k = 3, the output should be 3, 5, 9. I want to solve this problem in O(n) time.

My current solution is to have another array with only odd numbers and then I apply this algorithm which is by finding the median and divide the list into L, Median , Right and compare the k as the following: 

If |L|<k<= (|L|+|M|) Return the median 
else if K<|L|, solve the problem recursively on (L)
else work on (R, k- (|L|+|M|)

Any help is appreciated.

Solution

  • Assuming the output can be in any order:

    Create a separate array with only odd numbers.

    Use a selection algorithm to determine the k-th item. One such algorithm is quickselect (which runs in O(n) on average), which is related to quicksort - it partitions the array by some pivot, and then recursively goes to one of the partitioned sides, based on the sizes of each. See this question for more details.

    Since quickselect partitions the input, you will be able to output the results directly after running this algorithm (as Karoly mentioned).

    Both of the above steps take O(n), thus the overall running time is O(n).

    If you need the output in ascending order:

    If k = n, and all the numbers are odd, then an O(n) solution to this would be an O(n) sorting algorithm, but no-one knows of such an algorithm.

    To anyone who's considering disagreeing, saying that some non-comparison-based sort is O(n) - it's not, each of these algorithms have some other factor in the complexity, such as the size of the numbers.

    The best you can do here, with unbounded numbers, is to use the approach suggested in Proger's answer (O(n + k log n)), or iterate through the input, maintaining a heap of the k smallest odd numbers (O(n log k)).