class Questions::Issue20260302
Question
Find the majority element in an array (one that appears more than n/2 times) in O(n) time and O(1) space without hashmaps.
Hint: the Boyer-Moore Voting algorithm might help if you canβt figure this one out!
Examples
Public Instance Methods
Source
# File questions/20260302.rb, line 22 def setup @methods = Answers::Issue20260302.instance_methods(false) @examples = [ { array: [2, 2, 1, 1, 2, 2, 1, 2, 2], expected: 2, }, { array: [3, 3, 4, 2, 3, 3, 1], expected: 3, }, # Extra example by izkreny { array: %w[x o o], expected: "o", }, ] end
Tests
Public Instance Methods
Source
# File questions/20260302.rb, line 43 def test_answers_with_examples @methods.each do |method| @examples.each do |example| actual = public_send(method, example[:array]) assert_equal example[:expected], actual, "Answer #{method} is not correct" refute_same example[:array], actual, "Answer #{method} is messing with the array" end end end