Sum Of Four Values

May 31, 2023

Explanation

Here, we are given an array of n integers and we are told to find 4 numbers whose sum equals to target.

We can do this by getting all the possible sums of two elements and storing them with their indices. Now we have reduced this problem into Sum Of Two Values.

We'll find two values from the sums of two values whose sum equals target and their indices don't overlap.

Code

use std::io;

fn main() {
    let (n, target) = {
        let tmp = scan_vec::<i32>();
        (tmp[0] as usize, tmp[1])
    };
    let nums = scan_vec::<i32>();
    let mut sums = vec![];

    for i in 0..n {
        for j in i + 1..n {
            sums.push((nums[i] + nums[j], i + 1, j + 1));
        }
    }
    sums.sort();

    if sums.is_empty() {
        println!("IMPOSSIBLE");
        return;
    }

    if let Some(ans) = sum_of_two_values(target, &sums) {
        println!("{} {} {} {}", ans.0, ans.1, ans.2, ans.3);
    } else {
        println!("IMPOSSIBLE");
    }
}

fn sum_of_two_values(
    target: i32,
    nums: &Vec<(i32, usize, usize)>,
) -> Option<(usize, usize, usize, usize)> {
    let mut left = 0;
    let mut right = nums.len() - 1;

    while left < right {
        let (s1, i, j) = nums[left];
        let (s2, k, l) = nums[right];
        let sum = s1 + s2;
        if sum == target {
            if i != k && i != l && j != k && j != l {
                return Some((i, j, k, l));
            } else {
                right -= 1;
            }
        } else if sum < target {
            left += 1;
        } else {
            right -= 1;
        }
    }
    None
}

fn scan_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    input
        .trim()
        .split_whitespace()
        .map(|x| x.parse().ok().unwrap())
        .collect()
}