Skip to the content ForoHackers
Log inJoin

Puzzle: the element that appears more than n/2 times

AlgorithmsCompetitive programmingPuzzles
#980 · off_by_two · · Report

An array of n integers contains one value that appears more than n/2 times (a strict majority). Find it.

Constraints: one pass over the array, O(1) extra memory. No hash map, no sorting.

Example: [2, 7, 2, 2, 5, 2, 2, 7] gives 2 (5 of 8).

A hint without spoilers: pairs of different elements can cancel each other out.

Follow-up for later: what if there is no guarantee that a majority exists?

#1317 · hexdump_hermit · · Report

Spoiler. Keep candidate and count. For each x: if count == 0, set candidate = x, count = 1; else if x == candidate, count++; else count--. At the end candidate is the majority. Each decrement removes one majority element together with one non-majority element, and the majority has more than half, so it survives.

#1318 · regex_regret · · Report

Follow-up answer: if no majority is guaranteed, the survivor is only a candidate. Do a second pass counting it and compare against n/2. Two passes, still O(1) memory.

#1319 · off_by_two · · Report

Both right. Next level: elements appearing more than n/3 times. How many candidates do you need to track?

#1320 · hexdump_hermit · · Report

Two. At most two values can exceed n/3. Same cancelling idea, triple instead of pair, plus a verification pass.

Log in or join to reply.