C to find a missing integer in a sequence of numbers
You are given a sequence of n-1 distinct positive integers, each less than or equal to an integer n. You must find an integer that is not in the range [1,2, ..., n]. Solve the issue without using arrays.
Input format: One line containing integer n, where 2 <= n <= 10000 The 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 the code 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?
source to share
The logic is simple. You just find the sum of continuous numbers sequentially for a given n.
And now add all the numbers given in the question to find the exact sum of the given numbers.
The difference is that you can say that the difference between the two amounts is the missing number.
Ex: - Let's say n = 6.
So, you just find the sum of n consecutive integers starting with 1, ..., 6: - 6 * (6 + 1) / 2 = 21. The formula for the sum of n consecutive integers starting with 1 is {n * ( n + 1)} / 2.
And now find the sum of the given n-1 numbers.
Let's say the numbers are listed as 1,2,4,5,6. Then their sum = 1 + 2 + 4 + 5 + 6 = 18.
Therefore, the missing number = the sum of continuous n numbers - the sum of the given (n-1) numbers = 3.
source to share
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 the answer = 55 - (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 10) = 9.
source to share
To find the missing number in an array from 1 to n-1, then we have two methods, one is the sum formula and the other is the XOR method, where both give O (n) time complexity.
Use sum formula
1 Get the sum of numbers
total = n*(n+1)/2
2 Subtract all numbers from the sum and you get the missing number.
Use XOR method
1 XOR all elements of the array, let the XOR result be X1.
2 XOR all numbers from 1 to n, let XOR - X2.
3 XOR X1 and X2 gives the missing number.
source to share
'You can use the sum method as the sum of the total numbers in the array, since the total size of the array is 5 and the elements are 1,2,4,5,6, then size = 5, then use this method (n (n + 1) ) / 2 n = 5 here, so 15 is calculated again the sum of array elements 1 + 2 + 4 + 5 + 6 = 18 so 18-15 = 3 simple "
source to share