Quiz on DSA Series

Following questions/quizzes are taken from our Instagram Page.

---

We can solve this problem using many methods but we are looking for optimal method.

How to solve this problem?

• We have to find missing numbers from a given integer array of 1 to 100.
• Of-course array data structure is useful to store the integers.

If Only one number is missing from the array of 1 to 100:

Formula to find sum of first n natural numbers is n*(n+1)/2 .
1. First of all we will find sum of first 100 natural numbers and sum of numbers from the array.
2. Then we will subtract first sum with second sum, we will get the missing number.
3. This method will work if only one number is missing from the array .

//C Program
#include<stdio.h>

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 9, 10};   
    //for this program we will consider 1 to 10 numbers only
    int n = 10, i; 
    
    int sum1 = n*(n+1)/2;
    
    int sum2 = 0;
    for(i=0; i<n-1; i++)
        sum2 += arr[i];
        
    printf("Missing number is: %d", sum1-sum2);
 
    return 0;   
}

#python code

arr = [1, 2, 3, 4, 5, 6, 7, 9, 10]
n = 10

sum1 = n*(n+1)//2

sum2 = 0
for number in arr:
    sum2 += number
    
print("Missing number is:", sum1-sum2)

---

If more than one numbers are missing from the array of 1 to 100:

Above method won’t work if there are more than one numbers are missing from the array.

We have multiple approaches to solve this problem.
First approach is sort the array in ascending order. And check for each iteration if count is equal to number in array or not. If not display that number.

//pseudocode
arr.sort()
for i=0 to 100
{
    if i+1 != arr[i]
         print arr[i]  //missing number
}

Second approach is without sorting the array. But for this approach we need extra space to store count of numbers from 1 to 100.

//c program

#include<stdio.h>

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 7, 9, 10};   
    int lenOfArr = sizeof(arr)/sizeof(arr[0]);
    //for this program we will consider 1 to 10 numbers only
    int n = 10, i; 
    
    int missing[n+1]; 
    
    for(i=1; i<n+1; i++)
        missing[i] = 0;
    
    for(i=0; i<lenOfArr; i++)
       missing[arr[i]] = 1;
      
    printf("Missing number are: \n");
    for(i=1; i<n+1; i++)
    {
        if(missing[i] == 0)
            printf("%d\t", i);
    }
    
    return 0;   
}

#python code

arr = [1, 2, 3, 4, 5, 7, 9, 10]
lenOfArr = len(arr)

n = 10

missing = [0 for _ in range(n+1)]

for number in arr:
    missing[number] = 1

print("Missing number are:")

for i in range(1, n+1):
    if missing[i] != 1:
        print(i)