linear.rs

fn main() {
}

/// Find a duplicate in array in O(N), with in-place modifications.
/// Iterate over the first N items. On meeting a value {v}, try to insert it
/// to index {v}, but before that, check if {input[v] == v} - if yes, return {v} as
/// the answer.
/// Finally, if nothing was found, then by birthday paradox, the last element repeats
/// some other element in the array.
fn solve(mut input: Vec<i32>) -> i32 {

    // Rust does not allow iterating over the array and modifying it at the same time,
    // therefore one is forced to rely on idices.
    for i in 0..input.len() {
        let alleged_repeated = input[i as usize];
        // nested square-bracket access is not allowed in Rust.
        if input[alleged_repeated as usize] == i as i32 {
            return i as i32;
        }
        input[alleged_repeated as usize] = i as i32;
    }

    input[input.len() - 1]
}