Find The Missing Ids - Leetcode Solution

Problem Statement: Given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in the list. One of the integers is missing in the list. Write an efficient code to find the missing integer.

Solution:

To solve this problem, we can use the concept of finding the sum of n natural numbers. The sum of n natural numbers is given by the formula n*(n+1)/2. We can subtract the sum of all the given numbers from this sum to get the missing number.

1. Calculate the sum of first n natural numbers using the formula n*(n+1)/2.

2. Calculate the sum of all the given numbers.

3. Subtract the sum of all the given numbers from the sum of first n natural numbers.

4. The result obtained is the missing number.

Let's code the same.

class Solution { public: int missingNumber(vector<int>& nums) { int n=nums.size(); int sum=n*(n+1)/2; int sumOfNums=0; for(int i=0;i<n;i++){ sumOfNums+=nums[i]; } return sum-sumOfNums; } };

Time complexity: O(n) Space complexity: O(1)

Note: This solution assumes that there is only one missing number in the list. If there are multiple missing numbers in the list, this solution will not work.

1