Write a c program to find missing number in array. Given an array of numbers from 1 to n. The array is sorted. One number is missing from an array. You have to write a c code to find the missing number from an array. Also ,there is no duplicates in an array. This type of questions is generally asked in technical interviews.
There are multiple approaches to solve this problem. Here, I am going to explain two approaches to solve this problem and both the solution take O(n) time complexity.
Programming Questions on Array
How to Find Missing Number in Array
Logic–
1. As per problem statement, we have an array of 1 to n numbers and there is no duplicate number in an array. One number is missing from an array and we have to find it.
Let’s first calculate the sum of 1 to n numbers. We can calculate easily by using sum of the series formula.
|
1 |
sum = n*(n+1)/2; |
2. In next step, add all the numbers of an array. Let’s take the value of n = 100.
|
1 2 3 |
for (i=0; i<n; i++){ sum_of_num += arr[i]; } |
Now, we have the sum of 100 numbers and sum of all the numbers of an array.
If we subtract the sum of 100 numbers to the sum of all the numbers in an array we get the missing number.
|
1 |
missing_number = sum - sum_of_num; |
Time complexity of this problem is O(n).
C Program to Find Missing Number in Array
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <stdio.h> int main() { int i; /* Let's assume input array a is */ int a[] = {1,2,3,4,5,6,7,9,10}; /* Array of 1 to 10 numbers, so n is 10 */ int n = 10; /*Initialize total and sum variable */ int total=0,sum=0; /* calculate sum of 10 numbers. */ total = (n*(n+1))/2; /* Sum of input array element. */ for(i=0 ; i<n; i++){ sum = sum + a[i]; } printf("Missing number is %d",total-sum); return 0; } |
