#include <stdio.h>

int dominator( int *values, int length );

void test( int expect, int *data, int length )
{
    int result = dominator(data, length);
    printf("result: %i (%s)\n", result, (result == expect) ? "PASS" : "FAIL");
}

int main(int argc, char *argv[])
{
    int test1[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10 };
    int test2[] = { 10, 9, 10, 7, 10, 5, 10, 3, 10, 1, 10, -2, 10, -4, 10, -6, 10, -8, 10, 10 };
    int test3[] = { -4234, 12312412, -4234, -4234, 0xFFFFFF, -4234, 0xFFFFF, -4234, 10, -4234, -4235, 
                    -4234, 234234, 234234, -4234, -4234, -4234, -8, 10 };
    int test4[] = { 0xFFFE, 0xFFFC, 0xFFFD, 0xFFFC, 0xFFFE, 0xFFFF, 0xFFFC, 0xFFFD, 0xFFFB };

    test(-1, test1, sizeof(test1)/sizeof(int));
    test(10, test2, sizeof(test2)/sizeof(int));
    test(-4234, test3, sizeof(test3)/sizeof(int));
    test(-1, test4, sizeof(test4)/sizeof(int));
}

int dominator( int *values, int length )
{
    unsigned int mask = 0x80000000;
    unsigned int pattern = 0;
    int count = 0;
    int i;
    while (mask) { /* this loops through a fixed 32 times (once for each bit assuming 32bit ints) */
        count = 0;
        for ( i = 0; i < length; i++ ) { /* will iterate 32 * length times to give an O(n) complexity */
            count += ( ((unsigned int)values[i]) & mask ) ? 1 : 0;
        }
        if ( count > (length/2) ) {
            pattern |= mask;
        }
        mask >>= 1;
    }
    count = 0;
    for ( i = 0; i < length; i++ ) { /* will iterate an extra 1 * lengths times, total is
                                            looping 33 * length times which is still O(n) */
        count += ( ((unsigned int)values[i]) == pattern ) ? 1 : 0;
    }
    if ( count > (length/2) ) {
        return (int)pattern;
    }
    return -1;
}