Question

We are given a non sorted array so that the values are not pairwise disjoint (the same values may appear in many entries). Say that we can find the k-th smallest element number in the array in time O(n) for any 1 <= k <= n. Give an algorithm that finds if there is a value that appears at least n/3 times.

Please explain the algorithm in words and analyze the run time.

Answer 1

The algorithm is based upon moore voting algorithm to find majority element in an array.

Algorithm->

NBY3COUNT(arr[1..n], n)

count1 = 0, count2 = 0 //simple counter for candidates

first=second=None //there can be at max two elements with at least count>n/3 these are candidates

    for i = 1 to n do

        // if this element is previously seen, increment count1.

        if first = arr[i] then count1++;

        // if this element is previously seen, but not same as first, increment count2.

        else if second = arr[i] then count2++;

//if we haven't assigned first number or previously assigned may not be correct

        else if count1 = 0 then count1++ ,  first = arr[i]

//same for second number

        else if count2 = 0) then count2++, second = arr[i];

        // if current element is different from both the previously seen variables,then decrement both the counts.

        else  count1--,   count2--

end //for loop

    count1 = count2 = 0 //counting the occurrence of first and second

    // Again traverse the array and find the actual counts (verifying if the numbers exist).

    for i=1 to n do

        if arr[i] = first then count1++;

        else if arr[i] = second then count2++;

end //for loop

  

    if count1 > n / 3 or count2> n/3 the return TRUE

return FALSE

end //function

------------------------------------------

Time Complexity O(n) two linear passes only through the array