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?
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments