094_single_number.sio

//@ run-pass
// HumanEval 094: Single Number
//
// Given an array where every element appears twice except for one,
// find the element that appears only once. Uses XOR: a ^ a = 0 and
// a ^ 0 = a, so XOR of all elements cancels pairs and leaves the unique one.
// O(n) time, O(1) space.

fn single_number(arr: [i64; 256], n: i64) -> i64 with Mut, Panic {
    var result: i64 = 0
    var i: i64 = 0
    while i < n {
        result = result ^ arr[i]
        i = i + 1
    }
    result
}

fn main() -> i64 with IO, Mut, Panic, Div {
    // Test 1: [2, 2, 1] -> 1
    var a1: [i64; 256] = [0; 256]
    a1[0] = 2
    a1[1] = 2
    a1[2] = 1
    assert(single_number(a1, 3) == 1)

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

    // Test 3: [1] -> 1
    var a3: [i64; 256] = [0; 256]
    a3[0] = 1
    assert(single_number(a3, 1) == 1)

    // Test 4: [7, 3, 5, 3, 7] -> 5
    var a4: [i64; 256] = [0; 256]
    a4[0] = 7
    a4[1] = 3
    a4[2] = 5
    a4[3] = 3
    a4[4] = 7
    assert(single_number(a4, 5) == 5)

    // Test 5: [0, 1, 0] -> 1
    var a5: [i64; 256] = [0; 256]
    a5[0] = 0
    a5[1] = 1
    a5[2] = 0
    assert(single_number(a5, 3) == 1)

    // Test 6: [100, 200, 100, 300, 200, 400, 300] -> 400
    var a6: [i64; 256] = [0; 256]
    a6[0] = 100
    a6[1] = 200
    a6[2] = 100
    a6[3] = 300
    a6[4] = 200
    a6[5] = 400
    a6[6] = 300
    assert(single_number(a6, 7) == 400)

    // Test 7: [42] -> 42
    var a7: [i64; 256] = [0; 256]
    a7[0] = 42
    assert(single_number(a7, 1) == 42)

    // Test 8: [10, 20, 10, 30, 20, 30, 99] -> 99
    var a8: [i64; 256] = [0; 256]
    a8[0] = 10
    a8[1] = 20
    a8[2] = 10
    a8[3] = 30
    a8[4] = 20
    a8[5] = 30
    a8[6] = 99
    assert(single_number(a8, 7) == 99)

    println("094_single_number: ALL TESTS PASSED")
    0
}