We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Divisible Sum Pairs
  2. Discussions

Divisible Sum Pairs

  • victor_reial
     + 0 comments

    Rust best solution


    If you’re looking for solutions to the 3-month preparation kit in either Python or Rust, you can find them below: my solutions 

    pub fn divisible_sum_pairs(n: i32, k: i32, ar: &[i32]) -> i32 {
    //Time complexity: O(n+k)
    //Space complexity (ignoring input): O(k)
    let mut remainder_dictionary = std::collections::HashMap::new();
    for number in ar {
        let remainder = number % k;
        match remainder_dictionary.get(&remainder) {
            Some(n) => remainder_dictionary.insert(remainder, n + 1),
            None => remainder_dictionary.insert(remainder, 1),
        };
    }

    let mut total_pairs = 0;
    //For remainders 0 and k/2, the total pairs will be n choose 2
    println!(
        "->> remainder_dictionary <<- function: divisible_sum_pairs; file: week1.rs\n{:?}",
        remainder_dictionary
    );
    total_pairs += match remainder_dictionary.get(&0) {
        Some(n) => n * (n - 1) / 2,
        None => 0,
    };
    let k_is_pair = k % 2 == 0;
    if k_is_pair {
        total_pairs += match remainder_dictionary.get(&(k / 2)) {
            Some(n) => n * (n - 1) / 2,
            None => 0,
        };
    }

    for remainder in 1..(k + 1) / 2 {
        total_pairs += remainder_dictionary.get(&remainder).unwrap_or(&0)
            * remainder_dictionary.get(&(k - remainder)).unwrap_or(&0);
    }

    total_pairs
}