paint-brush
Contains Duplicate and Missing Numberby@deft
608 reads
608 reads

Contains Duplicate and Missing Number

by Sergey GolitsynOctober 8th, 2022
Read on Terminal Reader
Read this story w/o Javascript
tldt arrow

Too Long; Didn't Read

Problem solved by Sergei Golitsyn: “Given an integer array `nums` returns `true` if any value appears at least twice in the array, and return `false`’s if every element is distinct in the array. 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. If we find a sum for one of the elements from 1 to 3 to 3, we will have an array like \[1,2,3,1]
featured image - Contains Duplicate and Missing Number
Sergey Golitsyn HackerNoon profile picture

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