Find the Missing Number in an Array

In this article, I explained about how to find the missing number in an array.

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:
Your algorithm should run in linear run time complexity. Could you implement it using only constant extra space complexity?

Basic Knowledge

Find the sum of 1 to 10 numbers?

Formula :

sum = n * (n + 1) / 2;

sum = 10 * (10 + 1) / 2;

Steps to solve

Step 1

  • With the above formula of how to find the sum of given length, find the sum for length of an array.
  • If the size of an array is 10, then sum will be 55.

Step 2

  • Find the actual sum of the array. i.e if array has {3,0,1} then actual sum will be 4;

Step 3

  • Consider array has {3, 0, 1}, the actual sum will be 4.
  • The length of an array, here is 2.
  • Calculate the sum for length 2, that is 2 * (2+1)/2 = 2;
  • Find the difference of sum and actual sum, that’s the answer.
  • sum – actual sum = 4 – 2 = 2.
  • So, 2 is the missing number, we got the answer here.

Solution

Java Program

class Solution {
    public int missingNumber(int[] nums) {
        
        //Finding total sum of an array
        int sum = nums.length * (nums.length+1)/2;
        
        int actualSum = 0;
        //Calculate the actual sum
        for(int n : nums)
        {
            actualSum += n;
        }
        
        //missing number
        return sum-actualSum;
    }
}

Time Complexity : O(n)

Space Complexity : O(1)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s