C# Program to Find Missing Number in Array

You can find the missing number in an array by calculating the expected sum with n*(n+1)/2 and subtracting the actual sum of array elements, like int missing = totalSum - actualSum;.

Examples

Input[1, 2, 4, 5, 6]

Output3

Input[1, 3]

Output2

Input[2, 3, 4, 5]

Output1

How to Think About It

To find the missing number, first understand that the array should contain numbers from 1 to n with one missing. Calculate the total sum of numbers from 1 to n using the formula n*(n+1)/2. Then find the sum of the given array elements. The difference between these two sums is the missing number.

Algorithm

1

Get the length of the array and add 1 to find n (the total count including the missing number).

2

Calculate the expected total sum of numbers from 1 to n using the formula n*(n+1)/2.

3

Calculate the sum of all elements in the given array.

4

Subtract the actual sum from the expected total sum to find the missing number.

5

Return or print the missing number.

Code

csharp

using System;
class Program {
    static void Main() {
        int[] arr = {1, 2, 4, 5, 6};
        int n = arr.Length + 1;
        int totalSum = n * (n + 1) / 2;
        int actualSum = 0;
        foreach (int num in arr) {
            actualSum += num;
        }
        int missing = totalSum - actualSum;
        Console.WriteLine(missing);
    }
}

Output

3

Dry Run

Let's trace the example array [1, 2, 4, 5, 6] through the code

1

Calculate n

Array length is 5, so n = 5 + 1 = 6

2

Calculate total sum

totalSum = 6 * (6 + 1) / 2 = 21

3

Calculate actual sum

Sum of array elements = 1 + 2 + 4 + 5 + 6 = 18

4

Find missing number

missing = totalSum - actualSum = 21 - 18 = 3

Step	Value
n	6
totalSum	21
actualSum	18
missing	3

Why This Works

Step 1: Calculate expected sum

Using the formula n*(n+1)/2 gives the sum of all numbers from 1 to n, which is what the array should contain if no number was missing.

Step 2: Sum actual array elements

Adding all elements in the array gives the sum of the numbers present.

Step 3: Subtract to find missing

The difference between the expected sum and actual sum is the missing number because that number was not added in the actual sum.

Alternative Approaches

Using XOR operation

csharp

using System;
class Program {
    static void Main() {
        int[] arr = {1, 2, 4, 5, 6};
        int n = arr.Length + 1;
        int xorAll = 0;
        for (int i = 1; i <= n; i++) {
            xorAll ^= i;
        }
        int xorArr = 0;
        foreach (int num in arr) {
            xorArr ^= num;
        }
        int missing = xorAll ^ xorArr;
        Console.WriteLine(missing);
    }
}

This method uses bitwise XOR to find the missing number without sum calculation, which can avoid overflow for large n.

Using boolean array to mark presence

csharp

using System;
class Program {
    static void Main() {
        int[] arr = {1, 2, 4, 5, 6};
        int n = arr.Length + 1;
        bool[] present = new bool[n + 1];
        foreach (int num in arr) {
            present[num] = true;
        }
        int missing = 0;
        for (int i = 1; i <= n; i++) {
            if (!present[i]) {
                missing = i;
                break;
            }
        }
        Console.WriteLine(missing);
    }
}

This method uses extra space to track which numbers appear, useful if numbers are not guaranteed to be sorted.

Complexity: O(n) time, O(1) space

Time Complexity

The program loops through the array once to sum elements, so it runs in linear time relative to the array size.

Space Complexity

Only a few variables are used for sums and counters, so the space used is constant.

Which Approach is Fastest?

The sum formula method and XOR method both run in O(n) time and O(1) space, but XOR avoids overflow risk.

Approach	Time	Space	Best For
Sum formula	O(n)	O(1)	Simple and fast for small to medium arrays
XOR operation	O(n)	O(1)	Avoids overflow, good for large numbers
Boolean array	O(n)	O(n)	When numbers are unsorted or duplicates exist