LeetCode Entry

645. Set Mismatch

22.01.2024 easy 2024 kotlin rust

Return missing and duplicated number in 1..n array with one number replaced.

645. Set Mismatch easy blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/480

Problem TLDR

Return missing and duplicated number in 1..n array with one number replaced.

Intuition

First try to find a xor solution by observing xor differencies. Then give up and just compare sorted order or even better HashSet with expected.

Approach

  • delta sums is a trivial approach, use it in an interview
  • learn about xor solution (homework)

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


  fun findErrorNums(nums: IntArray) = with(nums) {
    val missing = ((1..size) - toSet()).first()
    val delta = sum() - (size + 1) * size / 2
    intArrayOf(missing + delta, missing)
  }



  pub fn find_error_nums(nums: Vec<i32>) -> Vec<i32> {
    let sz = nums.len() as i32;
    let sum: i32 = nums.iter().sum();
    let set_sum: i32 = nums.into_iter().collect::<HashSet<_>>().iter().sum();
    vec![sum - set_sum, sz * (sz + 1) / 2 - set_sum]
  }