leet-code/first-missing-positive/sol.rs

struct Solution {}

// TODO: Incomplete
impl Solution {
    pub fn first_missing_positive(nums: Vec<i32>) -> i32 {
        let (count, max, sum) = nums
            .iter()
            .fold((0, 0, 0), |(count, max, sum), n| {
                if *n > 0 {
                    return (count + 1, if *n > max { *n } else { max }, sum + *n);
                }
                (count, max, sum)
            });
        let expected_sum = max * (max + 1) / 2;
        let missing = max - count;
        let diff = expected_sum - sum;
        if diff == 0 {
            max + 1
        } else if missing == 1 {
            diff
        } else {
            let min_k = missing * (missing - 1) / 2;
            (1..).find(|&n| {
                let k = diff - n * missing;
                k >= min_k && n + k - min_k + missing <= max
            }).unwrap()
        }
    }
}

fn main() {
    println!("{}", Solution::first_missing_positive(vec![7,9,10])); // n = 1, m = 7, k = 22
    println!("{}", Solution::first_missing_positive(vec![6,5,-1,2,4,3,1])); // n = 7, m = 1, k = 0
    println!("{}", Solution::first_missing_positive(vec![4,-1,1])); // n = 2, m = 2, k = 1
    println!("{}", Solution::first_missing_positive(vec![4,6,-1,1])); // n = 2, m = 3, k = 4
    println!("{}", Solution::first_missing_positive(vec![2,2])); // n = 2, m = 3, k = 4
}