034_majority_element.sio

//@ run-pass
// HumanEval 034: Majority Element (Boyer-Moore Voting Algorithm)
//
// Find the element that appears more than n/2 times in the array.
// Phase 1: Find a candidate using Boyer-Moore voting.
// Phase 2: Verify the candidate actually has majority count.
// Returns the majority element, or -1 if none exists.

fn majority_element(arr: [i64; 256], n: i64) -> i64 with Mut, Panic, Div {
    // Phase 1: Boyer-Moore voting
    var candidate: i64 = arr[0]
    var count: i64 = 1
    var i: i64 = 1
    while i < n {
        if count == 0 {
            candidate = arr[i]
            count = 1
        } else if arr[i] == candidate {
            count = count + 1
        } else {
            count = count - 1
        }
        i = i + 1
    }

    // Phase 2: verify candidate
    var verify_count: i64 = 0
    var j: i64 = 0
    while j < n {
        if arr[j] == candidate {
            verify_count = verify_count + 1
        }
        j = j + 1
    }

    if verify_count > n / 2 {
        candidate
    } else {
        0 - 1
    }
}

fn main() -> i64 with IO, Mut, Panic, Div {
    // Test 1: [3, 3, 4, 2, 3, 3, 3] -> majority is 3
    var a1: [i64; 256] = [0; 256]
    a1[0] = 3
    a1[1] = 3
    a1[2] = 4
    a1[3] = 2
    a1[4] = 3
    a1[5] = 3
    a1[6] = 3
    assert(majority_element(a1, 7) == 3)

    // Test 2: [1, 1, 1, 2, 2] -> majority is 1
    var a2: [i64; 256] = [0; 256]
    a2[0] = 1
    a2[1] = 1
    a2[2] = 1
    a2[3] = 2
    a2[4] = 2
    assert(majority_element(a2, 5) == 1)

    // Test 3: [2, 2, 2, 2] -> majority is 2
    var a3: [i64; 256] = [0; 256]
    a3[0] = 2
    a3[1] = 2
    a3[2] = 2
    a3[3] = 2
    assert(majority_element(a3, 4) == 2)

    // Test 4: [1, 2, 3, 4] -> no majority, returns -1
    var a4: [i64; 256] = [0; 256]
    a4[0] = 1
    a4[1] = 2
    a4[2] = 3
    a4[3] = 4
    assert(majority_element(a4, 4) == 0 - 1)

    // Test 5: single element [7] -> majority is 7
    var a5: [i64; 256] = [0; 256]
    a5[0] = 7
    assert(majority_element(a5, 1) == 7)

    println("034_majority_element: ALL TESTS PASSED")
    0
}