Loading page…
Practice problem · easy
A bank app records which payment method each checkout used. The method is a code: 0 for card, 1 for bank transfer, 2 for wallet, and so on up to 1000 for the rarest ones.
On busy days one method is used by more than half of all checkouts. Your team lead asks you to find that method from the day's list.
Write majority_method(methods).
methods[i] is the method code of the i-th checkout.methods.length / 2 times. It is guaranteed to exist.Input: methods = [2, 1, 2, 2, 1]
Output: 2The trace counts each code as it is read and stops when a count passes half of 5, rounded down, which is 2. The last checkout is never read.
| i | code | Counts after | Above 2? |
|---|---|---|---|
| 0 | 2 | 2: 1 | no |
| 1 | 1 | 2: 1, 1: 1 | no |
| 2 | 2 | 2: 2, 1: 1 | no |
| 3 | 2 | 2: 3, 1: 1 | yes: return 2 |
Code 2 appears 3 times out of 5, which is more than half, so the answer is 2.
Input: methods = [7]
Output: 7One checkout, one code. It is the majority.
Input: methods = [0, 0, 1, 0, 2, 0, 1]
Output: 0Code 0 appears 4 times out of 7, which is more than half.
1 ≤ methods.length ≤ 100,000 (checkouts in a day)0 ≤ methods[i] ≤ 1000 (method codes)methods.length / 2 times.Counting a checkout's code by scanning the whole list costs n steps. Doing that for every checkout costs n × n, about 10^10 at n = 100,000. A table of counts reads the list once, which is 100,000 steps, and with codes up to 1,000 it can be a plain array of 1,001 counters. The guarantee that a majority exists means you never have to handle "no answer".
majority_method · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.