Majority Element Finder

Given an array of n integers, find the majority element - the element that appears strictly more than floor(n/2) times. It is guaranteed that the array always has a majority element. Solve it in O(n) time using O(1) extra space with a voting-based search technique rather than sorting or hash counting.

Input: The first line contains the integer n. The second line contains n space-separated integers, the array. Output: Print a single integer: the majority element.

1 <= n <= 10^5 -10^9 <= a[i] <= 10^9 A majority element is guaranteed to exist.

This is the classic O(1)-space alternative to a hash-map-based majority count - recognizing when a problem's guarantees (majority EXISTS) let you skip the safety-net verification pass that would otherwise be necessary.

Find the value appearing more than half the time in an array, using O(1) space instead of a hash map. Brute force: Use a hash map to count every value's occurrences directly - this works but costs O(n) extra space, when Boyer-Moore voting achieves the same result in O(1) space. Optimised: Boyer-Moore voting exploits the fact that a TRUE majority element (appearing more than n/2 times) can NEVER be fully 'cancelled out' by all other elements combined, since by definition it outnumbers everything else put together - tracking a single running candidate-and-counter pair finds it in one linear pass with no extra memory.

1. Keep a running 'candidate' and a 'count', both starting empty/zero. 2. Whenever count hits 0, adopt the CURRENT element as the new candidate. 3. Increment the count when you see the candidate again, DECREMENT it for anything else - this is the Boyer-Moore voting technique.

Time: O(n) - a single pass through the array. Space: O(1) - just a candidate variable and a counter, no hash map needed.

n = 1 (the single element is trivially the majority) and arrays where the majority element occupies most or all positions.

Be ready to explain that because a majority element is explicitly GUARANTEED here, no verification pass is needed after voting - if the guarantee weren't given, a second pass confirming the candidate's true count would be required, since some inputs without a genuine majority could still leave a candidate standing.