DEV Community

Cover image for Solution: Missing Number
seanpgallivan
seanpgallivan

Posted on

2 2

Solution: Missing Number

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.


Leetcode Problem #268 (Easy): Missing Number


Description:


(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?


Examples:

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.
Example 4:
Input: nums = [0]
Output: 1
Explanation: n = 1 since there is 1 number, so all numbers are in the range [0,1]. 1 is the missing number in the range since it does not appear in nums.

Constraints:

  • n == nums.length
  • 1 <= n <= 10^4
  • 0 <= nums[i] <= n
  • All the numbers of nums are unique.

Idea:


(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

The sum of the numbers from 1 to N is the Nth triangular number, defined as N * (N + 1) / 2. It stands to reason, then, that we can simply find the difference between the Nth triangular number and the sum of nums, which should be our missing number.


Javascript Code:


(Jump to: Problem Description || Solution Idea)

const missingNumber = nums =>
    nums.length * (nums.length + 1) / 2 - nums.reduce((a,c) => a + c)
Enter fullscreen mode Exit fullscreen mode

Python Code:


(Jump to: Problem Description || Solution Idea)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        return len(nums) * (len(nums) + 1) // 2 - sum(nums)
Enter fullscreen mode Exit fullscreen mode

Java Code:


(Jump to: Problem Description || Solution Idea)

class Solution {
    public int missingNumber(int[] nums) {
        return nums.length * (nums.length + 1) / 2 - Arrays.stream(nums).sum();
    }
}
Enter fullscreen mode Exit fullscreen mode

C++ Code:


(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        return nums.size() * (nums.size() + 1) / 2 - accumulate(nums.begin(), nums.end(), 0);
    }
};
Enter fullscreen mode Exit fullscreen mode

Neon image

Set up a Neon project in seconds and connect from a Python application

If you're starting a new project, Neon has got your databases covered. No credit cards. No trials. No getting in your way.

Get started →

Top comments (3)

Collapse
 
nithish_13 profile image
Nithish Kumar

Hey sean , Thank you for sharing this problem. I really like it. After seeing the problem des. , i came up with this solution. Is this a better approach?

const findMissing = arr => {
const orginal = Array.from({length:arr.length+1} , (_,i) => i);
return orginal.filter(v => arr.indexOf(v) === -1)[0]
}

Thanks in advance :)

Collapse
 
seanpgallivan profile image
seanpgallivan • Edited

The code is very readable, which is good, but indexOf() is an O(n) time function by itself, so the overall time complexity becomes O(n^2), and the space complexity becomes O(n) since you're creating a new array (original).

Collapse
 
nithish_13 profile image
Nithish Kumar

Thank you for explaining... Even though I'm not good at Big O notation, I can understand ur explanation.

Neon image

Next.js applications: Set up a Neon project in seconds

If you're starting a new project, Neon has got your databases covered. No credit cards. No trials. No getting in your way.

Get started →

👋 Kindness is contagious

Engage with a wealth of insights in this thoughtful article, cherished by the supportive DEV Community. Coders of every background are encouraged to bring their perspectives and bolster our collective wisdom.

A sincere “thank you” often brightens someone’s day—share yours in the comments below!

On DEV, the act of sharing knowledge eases our journey and forges stronger community ties. Found value in this? A quick thank-you to the author can make a world of difference.

Okay