Missing Number

Chaitra Rai

·

Follow

1 min read

·

Aug 10, 2021

--

Listen

Share

“Given an array of numbers in range (0,n) there would be only one number missing. Write code to find this missing number” (Full Question)

• As mentioned the values would range only from o to n.
• The numbers should be from start to n values where n is the length of the array
• You can add all the values in a set, a Treeset probably because we get the values stored in a sorted order
• once inserted you can check if the values from 1,n is present of not using contains method
• This algorithm would take O(n) time complexity to get the solution but there a space complexity of O(n) involved

public int missingNumber(int[] nums) {
        int n=nums.length;
        int miss=0;
        Set<Integer> set=new TreeSet();
        for(int i=0;i<n;i++){
            set.add(nums[i]);
        }
        for(int i=1;i<=n;i++){
            if(!set.contains(i))
                miss=i;
        }
        return miss;
 }

• Lets see if we can avoid the extra space and do it modifying the existing array only
• There is a straight forward solution for this problem
• Gauss’s mathematical formula to get the sum of n numbers: n*(n+1)/2 would give the some of continuous n numbers from 0 or 1.
• we use this very formula to calculate the actual sum and then subtract this with the sum we get adding up the inputs
• this way the the missing number is found out

public int missingNumber(int[] nums) {
        int actual_sum=nums.length*(nums.length+1)/2;
        int sum=0;
        for(int x:nums)
            sum += x;
        return actual_sum-sum;
    }

• This is the solution for doing this problem with O(1) space complexity and O(n) time complexity