A. MEXanized Array

and solution of this problem with proof in Rust Language

Introduction

In this article, we will see my solution to the codeforces problem, 1870A. MEXanized Array, which came in Codeforces CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!).

Note : My Solution might not be the most optimized one, but it is certainly working.

You can go to above link to view the question statement.

Approach

In this problem, we can create a vector of integers, and push all the elements from 0 to mex-1. Then, we have to push maximum element, which is not mex.

Then, we check if all the conditions satisfy. If yes, we find the sum of the array and print it. Else, we print -1.

It is basically a Brute Force Approach, and uses O(N) time and space complexity, ( I know it can be achieved in O(1) too)

Proof

We must include all the elements less than mex at least once. Also, we check all the conditions. Hence, we can proof that this is correct answer.

Program

/*
This template is made by Naman Garg <[email protected]>
GitHub : https://github.com/namanlp
GitLab : https://gitlab.com/namanlp
Website : https://rustp.org

You can visit https://rustp.org/basic-programs/basic-template/
for understanding the template

Feel free to copy the template, but not the solutions :D
Thank You
 */

#![allow(unused)]

use std::io::stdin;

fn take_int() -> usize {
    let mut input = String::new();
    stdin().read_line(&mut input).unwrap();
    return input.trim().parse().unwrap();
}

fn take_vector() -> Vec<usize> {
    let mut input = String::new();
    stdin().read_line(&mut input).unwrap();
    let arr: Vec<usize> = input.trim().split_whitespace().map(|x| x.parse().unwrap()).collect();
    return arr;
}

fn take_string() -> Vec<char> {
    let mut input = String::new();
    stdin().read_line(&mut input).unwrap();
    let vec: Vec<char> = input.trim().chars().collect();
    return vec;
}

fn to_string(vec: Vec<char>) -> String { return vec.iter().collect::<String>(); }

fn solve() {
// ======================= Code Here =========================
    let n_k_x = take_vector();
    let n = n_k_x[0];
    let k = n_k_x[1];
    let x = n_k_x[2];

    let mut arr = Vec::new();

    if x+1 < k { println!("-1"); return; }

    for i in 0..k {
        arr.push(i);
    }

    while arr.len() < n {
        if x == k {
            arr.push(x-1);
        }
        else {
            arr.push(x);
        }
    }

    if arr.len() > n{ println!("-1"); return; }

    let mut sum =0;

    for i in arr {
        sum += i;
    }
    println!("{}", sum);
}


pub fn main() {
    let t = take_int();
    for _ in 0..t { solve(); }
}

Conclusion

In this article, we discussed solution to Codeforces problem 1870A. MEXanized Array along with proof and program in Rust Language.

Thank You