**Question**

Got a phone interview recently. The question is how to find out an integer which appears more than 50% times in an array of integers. For example, [1 1 0 1 2] should return 1, while [1 1 0 2 3] should return nothing.

**Solution**

The basic idea is finding out a candidate before checking if it repeats more than enough times. The algorithm is described in a paper entitled "Finding Repeated Elements" by Misra and Gries. The algorithm consists of two steps. First, it identifies a candidate value. The candidate value either occurs >50% of the time or there is no element in the array that occurs >50% of the time. The second step verifies whether the candidate element does indeed occur >50% of the time. Here's the algorithm, implemented in C:

#define undefined (-1) int find_element(int array[], int n) { /* Step 1: Find the element that occurs >50% of the time, if there is one. */ int c = 0; int candidate = undefined; for (int i = 0; i < n; i ++) { if (array[i] == candidate) /* Match. */ c += 2; else if (i == c) /* New candidate. */ { c += 2; candidate = array[i]; } } /* Step 2: Verify that the candidate actually occurs >50% of the time. */ for (i = 0, c = 0; i < n; i ++) if (array[i] == candidate) c ++; if (c * 2 > n) return candidate; else return undefined; }

## No comments:

## Post a Comment