Data Structures & Algorithms in Java – Binary – Missing Number

Problem:

Given an array with values between 1 to n , find the missing number between 1 to n that is not present in the array

Input:

[9,6,4,2,3,5,7,0,1]

Output:

8

In the above array of length 9 we have all the numbers from 1 to 9 except 8 , so output is 8

Try out the solution here:

https://leetcode.com/problems/missing-number

Solution:

Hint:

The sum of all numbers upto a given number n can be calculated using the formula:

(n * (n+1)/2)

Algorithm:

STEP1: Find the sum of all numbers upto the length of the given array using the formula (n*(n+1)/2) where n is the length of the array

STEP2: Find the sum of all numbers of the given array

STEP3: Find the difference between the sum calculated in step1 and that calculated in step2 , this gives the missing number

Code:

class Solution {
    public int missingNumber(int[] nums) {
        
   
        int sumGivenNos = 0;
        
        for(int i=0;i<nums.length;i++){
            
            sumGivenNos += nums[i];
        }
        
        return ((nums.length * (nums.length +1))/2) - sumGivenNos;
        
    }
}

Time complexity of above code is O(n) and space complexity is O(1)