Contains Duplicate and Missing Number

Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1:

Input: nums = [1,2,3,1]
Output: true

Example 2:

Input: nums = [1,2,3,4]
Output: false

Example 3:

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

Solution

As you know, choosing the correct data structure is a really important step in problem-solving.

“appears at least twice“ → means that we must check duplicates. How can we do it? Exactly, we can use a Set data structure for it.

We will iterate over the array and just check out the set; does it contain the current element? Otherwise, we have to save it into the set.

public boolean containsDuplicate(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int i : nums) {
        if (set.contains(i)) {
            return true;
        } else {
            set.add(i);
        }

    }
    return false;
}

And our next problem for today

Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Solution

We should find the missing number. From the description, we know that all elements are unique.

And for example, if we have arr length three, there must be 3 elements [1,2,3]. If we miss one of the elements, we will have an array like [1,0,3].

All elements in the array are static, which means if we find a sum for elements from 1 to 3 (6), it will be the same for the array from 3 to 1. Right? And finally, we can calculate a sum for a given array. And subtract it from the base sum.

public int missingNumber(int[] nums) {
    int realSum = 0;
    int sum = 0;

    for (int num : nums) {
        sum += num;
    }

    for (int i = 0; i <= nums.length; i++) {
        realSum += i;
    }
    return realSum - sum;
}

As an optimization, we can use only one for each loop as shown below

public int missingNumber(int[] nums) {
    int rez = 0;
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += (i + 1);
        rez += nums[i];
    }
    return sum - rez;
}

Thanks for reading and subscribe to my channel where we are trying to solve algo problems and talk about life in the USA → https://t.me/crack_code_interview