Find the Missing Number in an Array in C: A Comprehensive Guide

Introduction

In the world of programming, solving problems efficiently is a key skill. When it comes to working with arrays in the C language, one common challenge is to find the missing number in an array.

Whether you are a beginner or an experienced programmer, understanding different methods to tackle this problem is crucial.

Also Read: Insert and Delete Element in Array in C Using Switch Case

In this article, we will delve into various techniques, code examples, and step-by-step explanations to help you become proficient in finding the missing number in an array in C.

Find the Missing Number in an Array in C

To find the missing number in an array in C, you can explore multiple strategies that cater to different scenarios and array types. Below, we’ll discuss some of the most effective methods to accomplish this task.

Also Read: C Program To Read Two Files Simultaneously

Method 1: Sum of Integers

One of the simplest ways to find the missing number in an array is by calculating the sum of integers from 1 to N and then subtracting the sum of elements present in the array. The result will be the missing number.

// C code to find the missing number using sum of integers
#include <stdio.h>

int findMissingNumber(int arr[], int n) {
    int sum = (n * (n + 1)) / 2;
    for (int i = 0; i < n; i++) {
        sum -= arr[i];
    }
    return sum;
}

int main() {
    int arr[] = {1, 2, 4, 6, 3, 7, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Missing number is %d\n", findMissingNumber(arr, n));
    return 0;
}

Output

Missing number is 5

Also Read: Armstrong Number in C Programming

Method 2: XOR Operation

The XOR operation is another clever approach to find the missing number in an array. By XOR-ing all the elements in the array with the numbers from 1 to N, the duplicate numbers cancel out, leaving only the missing number.

// C code to find the missing number using XOR operation
#include <stdio.h>

int findMissingNumber(int arr[], int n) {
    int xorSum = 0;
    for (int i = 0; i < n; i++) {
        xorSum ^= arr[i] ^ (i + 1);
    }
    xorSum ^= (n + 1);
    return xorSum;
}

int main() {
    int arr[] = {1, 2, 4, 6, 3, 7, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Missing number is %d\n", findMissingNumber(arr, n));
    return 0;
}

Output

Missing number is 5

Method 3: Binary Search

When dealing with sorted arrays, a binary search approach can significantly improve the efficiency of finding the missing number.

Also Read: C Program to Find the Inverse of 2×2 Matrix

By dividing the array in half repeatedly and narrowing down the search space, we can pinpoint the missing number.

// C code to find the missing number using binary search
#include <stdio.h>

int findMissingNumber(int arr[], int n) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] - mid == 1) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return low + 1;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 7, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Missing number is %d\n", findMissingNumber(arr, n));
    return 0;
}

Output

Missing number is 6

Method 4: Hash Table

Using a hash table or an array to mark the presence of elements can also be employed to find the missing number.

Also Read: C Program to Copy the Contents of One File into Another File

By iterating through the array and marking each element’s occurrence, the missing number can be identified by locating the unmarked element.

// C code to find the missing number using a hash table
#include <stdio.h>

int findMissingNumber(int arr[], int n) {
    int hashTable[n + 1];
    for (int i = 0; i < n + 1; i++) {
        hashTable[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        hashTable[arr[i]] = 1;
    }
    for (int i = 1; i < n + 1; i++) {
        if (hashTable[i] == 0) {
            return i;
        }
    }
    return -1; // Handle edge case when no number is missing
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 7, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Missing number is %d\n", findMissingNumber(arr, n));
    return 0;
}

Output

Missing number is 6

Method 5: Gauss Formula

If the array contains only one missing number, you can utilize the Gauss formula to find it. The formula states that the sum of integers from 1 to N can be calculated using (N * (N + 1)) / 2.

Also Read: Getchar and Putchar Function in C with Example

By subtracting the sum of the array elements from the Gauss sum, you obtain the missing number.

// C code to find the missing number using Gauss formula
#include <stdio.h>

int findMissingNumber(int arr[], int n) {
    int sum = (n * (n + 1)) / 2;
    for (int i = 0; i < n; i++) {
        sum -= arr[i];
    }
    return sum;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 7, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Missing number is %d\n", findMissingNumber(arr, n));
    return 0;
}

Output

Missing number is 6

Also Read: C Program to Find the Sum of Cubes of Elements in an Array

FAQs

Conclusion

In conclusion, finding the missing number in an array in C is a fundamental problem in programming. We explored various efficient methods, including sum of integers, XOR operation, binary search, hash table, and Gauss formula, each catering to different scenarios.

Understanding these techniques empowers you to approach the problem with confidence and efficiency. Remember to analyze the array characteristics and choose the most suitable method for your specific scenario.

So go ahead and put your programming skills to the test! Finding the missing number in an array in C is an excellent exercise that sharpens your problem-solving abilities and boosts your confidence as a programmer.