Scribd
Upload
41 views2 pages

Missing Number in An Array

The document describes two methods to find the missing number in an array. The first method uses the summation formula to calculate the expected sum and compare it to the actual sum. The second method modifies the first to avoid integer overflow by subtracting one known number from the others.

Uploaded by

ayushi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
41 views2 pages

Missing Number in An Array

The document describes two methods to find the missing number in an array. The first method uses the summation formula to calculate the expected sum and compare it to the actual sum. The second method modifies the first to avoid integer overflow by subtracting one known number from the others.

Uploaded by

ayushi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

Missing Number in an array

Given an array of size N-1 such that it only contains distinct integers in the


range of 1 to N. Find the missing element.
Example 1:

Input:
N = 5
A[] = {1,2,3,5}
Output: 4

Example 2:

Input:
N = 10
A[] = {1,2,3,4,5,6,7,8,10}
Output: 9

Method 1: This method uses the technique of the summation formula. 


Approach: The length of the array is n-1. So the sum of all n elements, i.e sum of numbers from 1 to
n can be calculated using the formula n*(n+1)/2. Now find the sum of all the elements in the array
and subtract it from the sum of first n natural numbers, it will be the value of the missing element.

Method 2: Modification for Overflow  


Approach: The approach remains the same but there can be overflow if n is large. In order to avoid
integer overflow, pick one number from known numbers and subtract one number from given
numbers. This way there won't have Integer Overflow ever.

class GFG

{ static int getMissingNo(int a[], int n)

{ int total = 1;

for (int i = 2; i <= (n + 1); i++)

{ total += i;

total -= a[i – 2];

} return total; }

You might also like