C program to find missing integer in a sequence of numbers

Question

You are given a sequence of n-1 distinct positive integers, all of which are less than or equal to a integer ‘n’. You have to find the integer that is missing from the range [1,2,...,n]. Solve the question without using arrays.

Input Format: One line containing the integer ‘n’ where 2<=n<=10,000 First line is followed by a sequence of ‘n-1’ distinct positive integers. Note that the sequence may not be in any particular order.

I got code by using arrays

#include<stdio.h>
int main()
{
 int i,j,n[9999],m,t;
 scanf("%d",&m);
 for(i=1;i<m;i++)
 {
 scanf("%d",&n[i]);
 }
 for(i=1;i<m;i++)
 {
 for(j=1;j<i;j++)
 {
 if(n[j]>n[j+1])
 {
 t=n[j];
 n[j]=n[j+1];
 n[j+1]=t;
 }
 }
 }
 for(i=2;i<m;i++)
 {
 if(n[i-1]!=n[i]-1)
 {
 printf("%d",n[i]-1);
 break;
 }
 }
 return(0);
 }

How can I do the same without using arrays?

• Oliver Charlesworth: What would be the result of summing all the elements?
• BrunoLevy: It's a classical problem, see John Bentley "Programming Pearls" book. You may use a bitvector for keeping track of which number is there and which number is not there (but maybe this does not answer the question since a bitvector is somewhat an array...)
• Raymond Chen: Duplicate of How to Find Missing Number on Integer Array of 1 to 100?. Don't forget to cite this Web site when you submit your solution, so you aren't committing plagiarism.

Answer 1

The logic is simple. You just find the sum of the continuous numbers in series for a given n.

And, now add all those numbers provided in the question to find the sum exactly of the given numbers.

The difference is what you can say that difference between those 2 sums is the missing number.

Ex :- Let's say, n = 6.

So, you just find the sum of n consecutive integers starting from 1,...,6 is :- 6 * (6+1) / 2 = 21. Formula of sum of n consecutive integers starting from 1 is {n * (n+1)} / 2.

And, now find the sum of given n-1 numbers.

Say, numbers given are 1,2,4,5,6. Then their sum = 1 +たす 2 +たす 4 +たす 5 +たす 6 =わ 18.

Therefore, the missing number = sum of continuous n numbers - sum of given (n-1) numbers = 3.

Answer 2

Find the sum of the given integers. Subtract it from n(n+1)/2.

Explanation: The sum of the first n integers is n(n+1)/2. Therefore the sum of the given integers + missing integer= n(n+1)/2.

Suppose n=10;

Then, 1+たす2+たす3+たす4+たす5+たす6+たす7+たす8+たす9+たす10=わ10*(10+1)/2==55

If the given integers are- 1,2,3,4,5,6,7,8,10.

Then answer = 55 - (1+2+3+4+5+6+7+8+10)=9.

Answer 3

To find the missing number in the array of 1 to n-1 then we have two methods one is sum formula and second one is use XOR method where both gives O(n) time complexity.

Use Sum Formula

1 Get the sum of numbers

 total = n*(n+1)/2

2 Subtract all the numbers from sum and you will get the missing number.

Use XOR Method

1 XOR all the array elements, let the result of XOR be X1.

2 XOR all numbers from 1 to n, let XOR be X2.

3 XOR of X1 and X2 gives the missing number.

Answer 4

'You can use sum method as sum of total numbers in array as say total array size=5 and elements are 1,2,4,5,6 then size=5 then use this method (n(n+1))/2 n=5 here so 15 comes by calculation again sum of elements of array 1+2+4+5+6 =18 therefore 18-15=3 simple'