DSA Factory
Free Recursion lessonsRecursion · Stage 2 · Divide and conquer · Step 2

Who has more than half the votes

Find the value that fills more than half the list by finding each half's winner and counting both. About 14 minutes.

A winner must win a half

Votes are cast in a row, and a candidate wins only with more than half the votes. Split the row into a left half and a right half. If someone has more than half of everything, they can't be at or below half in both halves. So they must have more than half in at least one of them.

That gives two candidates at most: the winner of the left half and the winner of the right half. Find them recursively, then count each one over the whole range.

Whole winner: wins at least one half.
Two candidates: the winners of the halves.
In code
def count(lo, hi):
    if lo == hi:
        return 1 if nums[lo] == x else 0
    mid = (lo + hi) // 2
    a = count(lo, mid)
b = count(mid + 1, hi)
return a + b
Who has more than half of 3, 3, 3, 1, 2, 3, 1?
3
0
3
1
3
2
1
3
2
4
3
5
1
6
leftright

Split into 3, 3, 3, 1 and 2, 3, 1. A winner of the whole list must win one of these halves.

Move 1 of 4

Count to confirm

A half's winner might still lose over the whole range, so count. If both halves agree, that value wins the whole range, because it has more than half in each half. If they disagree, count each candidate over the whole range and keep the one with more than half.

If neither has more than half, nobody wins: return -1. A range with no winner reports -1, and that is a valid answer for the merge.

Same winner: it wins the whole range.
Different winners: count both over the whole range.
In code
total = 0
for v in nums[lo:hi + 1]:
    if v == cand:
        total += 1
size = hi - lo + 1
confirmed = total > size // 2
Quick check

Both halves have winner 5. Do you need to count anything over the whole range?

  1. ANo: 5 has more than half in each half, so more than half overall
  2. BYes, always count over the whole range
  3. COnly if the halves have different sizes
Show the answer

No: 5 has more than half in each half, so more than half overall. Two parts each above half add up to above half of the whole.

Your problem

Majority by halves

nums is a list of non-negative whole numbers. A majority value appears more than half the length times. Return the majority value, or -1 if there isn't one. Use a recursive function that splits the list in half.

Example
nums = [2, 2, 1, 1, 1, 2, 2] → 2

0 ≤ length ≤ 100,000 · 0 ≤ value ≤ 1,000,000,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve