Decimal dominant number in an array

Question

Recently i came across this interview question:

You are given n real numbers in an array. A number in the array is called a decimal dominant if it occurs more than n/10 times in the array. Give an O(n) time algorithm to determine if the given array has a decimal dominant.

Now i can think of a few ways to solve this, and any generalisation of this question (i.e. finding any number that appears K times in an array)

One could be to make a hash table in pass 1, and then count the number of occurences in pass 2, which would be O(n), but uses O(n) space as well,

There is one way using 9 buckets

But, is there any way we could do it in a constant space?? Any suggestions??

[EDIT] i haven't checked the 9 bucket solution, readers may like to go through n.m.'s comments below

Answer 1

Using 3-way qSort Java implementation printing

public class DecimalDominants {
    public static void sort(Comparable[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(Comparable[] arr, int lo, int hi) {
        if (lo >= hi) return;
        int lt = lo, gt = hi;
        Comparable v = arr[lo];
        int i = lo;
        while (i <= gt) {
            int cmp = arr[i].compareTo(v);
            if (cmp < 0) swap(arr, lt++, i++);
            else if (cmp > 0) swap(arr, i, gt--);
            else i++;
        }
        int times = gt - lt + 1;
        if (times > arr.length / 10) System.out.printf("%s repeats %d times\n", v, times);
        sort(arr, lo, lt - 1);
        sort(arr, gt + 1, hi);
    }

    private static void swap(Comparable[] arr, int i, int j) {
        Comparable swap = arr[i];
        arr[i] = arr[j];
        arr[j] = swap;
    }

    public static void main(String[] args) {
        Integer[] arr = {1, 2, 1, 2, 1, 2, 1, 4, 3, 2, 4, 2, 3, 5, 6, 7, 8, 9, 3, 2, 4, 5, 2, 3, 6, 7, 8, 3, 2, 5};
        System.out.println("print numbers which repeat more then " + arr.length / 10);
        sort(arr);
    }
}

Answer 2

you may use 3-way-partition quick-select to find the (n/10)th largest element of the array, and then check whether it's decimal-dominant; if not, recur in the right sub-array.

this can be done in-place and within linear expectation time, so not strictly constant space.