In an array containing numbers from 1 to N, where one number is missing, the goal is to find the missing number. Here, we'll discuss four different methods to achieve this, ranging from brute force to optimal approaches.

### Solution 1: Brute Force Approach (Using Nested Loop & Linear Search)

This approach involves checking for each number from 1 to N whether it exists in the array.

**Implementation**:

```
// Solution-1: Brute Force Approach (using Nested Loop & Linear Search)
// Time Complexity: O(n*n)
// Space Complexity: O(1)
int findMissingNumber(vector<int> &arr, int n)
{
// Outer loop that runs from 1 to N
for (int i = 1; i <= n; i++)
{
// `flag` variable to check if an element exists
bool flag = false;
// Search the element using Linear Search
for (int j = 0; j < n - 1; j++)
{
if (arr[j] == i)
{
flag = true;
break;
}
}
// Check if the element is missing
if (!flag)
{
return i;
}
}
// If loop completes without finding a missing number (shouldn't happen)
// It is just to avoid warnings.
return -1;
}
```

**Logic**:

**Outer Loop**: Iterate through numbers from 1 to N.**Linear Search**: For each number, check if it exists in the array using a nested loop.**Flag Check**: Use a flag to indicate if the number was found. If not, return the number as it is the missing one.

**Time Complexity**: O(n²)

**Explanation**: The outer loop runs from 1 to N and for each iteration of the outer loop, the inner loop runs up to N-1. This results in a time complexity of O(n * (n-1)), which simplifies to O(n²).

**Space Complexity**: O(1)

**Explanation**: Only a few additional variables (like`flag`

) are used, which do not depend on the size of the input array.

**Example**:

**Input**:`arr = [1, 2, 4, 6, 3, 7, 8]`

,`n = 8`

**Output**:`5`

**Explanation**: The number`5`

is missing from the array.

### Solution 2: Better Approach (Using Hashing)

This approach uses a hash table to track the presence of numbers in the array.

**Implementation**:

```
// Solution-2: Better Approach (using Hashing)
// Time Complexity: O(n) + O(n) ~ O(2n)
// Space Complexity: O(n)
int findMissingNumber(vector<int> &arr, int n)
{
// Hash table to store the presence of numbers
vector<int> hash(n + 1, 0);
// Mark the presence of elements in the hash table
for (int i = 0; i < n - 1; i++)
{
hash[arr[i]] = 1;
}
// Find the missing number by iterating through the hash table
for (int i = 1; i <= n; i++)
{
if (hash[i] == 0)
{
return i;
}
}
// If loop completes without finding a missing number (shouldn't happen)
// It is just to avoid warnings.
return -1;
}
```

**Logic**:

**Initialize Hash Table**: Create a hash table to track numbers from 1 to N.**Mark Presence**: Iterate through the array, marking the presence of each number in the hash table.**Find Missing Number**: Iterate through the hash table to find the number that is not marked.

**Time Complexity**: O(n)

**Explanation**: The first loop runs through the array of size N-1 to populate the hash table and the second loop runs through the hash table of size N to find the missing number. Thus, the overall time complexity is O(n) + O(n-1), which simplifies to O(n).

**Space Complexity**: O(n)

**Explanation**: An additional hash table of size N is used to keep track of the presence of each number.

**Example**:

**Input**:`arr = [1, 2, 4, 6, 3, 7, 8]`

,`n = 8`

**Output**:`5`

**Explanation**: The number`5`

is not present in the hash table.

### Solution 3: Optimal Approach 1 (Summation Approach)

This approach uses the sum formula for the first N natural numbers to find the missing number.

**Implementation**:

```
// Solution-3: Optimal Approach 1 (Summation Approach)
// Time Complexity: O(n)
// Space Complexity: O(1)
int findMissingNumber(vector<int> &arr, int n)
{
// Sum of all numbers from 1 to N
int sumOfNNums = (n * (n + 1)) / 2;
int sumOfArr = 0;
// Calculate the actual sum of elements in the array
for (int i = 0; i < n - 1; i++)
{
sumOfArr += arr[i];
}
int missingNum = sumOfNNums - sumOfArr;
return missingNum;
}
```

**Logic**:

**Sum of N Numbers**: Calculate the sum of numbers from 1 to N using the formula sum = (n * (n + 1)) / 2.**Sum of Array**: Calculate the sum of elements in the array.**Find Missing Number**: Subtract the sum of the array from the sum of N numbers to get the missing number.

**Time Complexity**: O(n)

**Explanation**: The loop runs through the array once to calculate the sum of the elements, resulting in a time complexity of O(n).

**Space Complexity**: O(1)

**Explanation**: Only a few additional variables (like`sumOfNNums`

and`sumOfArr`

) are used, which do not depend on the size of the input array.

**Example**:

**Input**:`arr = [1, 2, 4, 6, 3, 7, 8]`

,`n = 8`

**Output**:`5`

**Explanation**: The sum of numbers from`1`

to`8`

is`36`

and the sum of the array is`31.`

Thus, the missing number is`36 - 31 = 5`

.

### Solution 4: Optimal Approach 2 (XOR Approach)

This approach uses the XOR operation to find the missing number efficiently.

**Implementation**:

```
// Solution-4: Optimal Approach 2 (XOR Approach)
// Time Complexity: O(n)
// Space Complexity: O(1)
int findMissingNumber(vector<int> &arr, int n)
{
int xor1 = 0;
int xor2 = 0;
for (int i = 0; i < n - 1; i++)
{
// XOR of array elements
xor2 ^= arr[i];
// XOR up to [1...N-1]
xor1 ^= (i + 1);
}
// XOR up to [1...N]
xor1 ^= n;
// The missing number
return xor1 ^ xor2;
}
```

**Logic**:

**XOR Array Elements**: Compute the XOR of all elements in the array.**XOR Up to N**: Compute the XOR of all numbers from 1 to N.**Find Missing Number**: XOR the results from steps 1 and 2. The result will be the missing number.

**Time Complexity**: O(n)

**Explanation**: The first loop runs through the array of size N-1 to calculate the XOR of the elements and the second loop runs up to N to calculate the XOR of the range from 1 to N. Thus, the overall time complexity is O(n-1) + O(n), which simplifies to O(n).

**Space Complexity**: O(1)

**Explanation**: Only a few additional variables (like`xor1`

and`xor2`

) are used, which do not depend on the size of the input array.

**Example**:

**Input**:`arr = [1, 2, 4, 6, 3, 7, 8]`

,`n = 8`

**Output**:`5`

**Explanation**: XOR of all array elements and XOR of numbers from`1`

to`8`

will result in the missing number, which is`5`

.

### Comparison

**Brute Force Approach**:**Pros**: Simple and easy to understand.**Cons**: Inefficient with O(n²) time complexity.

**Hashing Approach**:**Pros**: More efficient with O(n) time complexity.**Cons**: Uses extra space for the hash table.

**Summation Approach**:**Pros**: Very efficient with O(n) time complexity and O(1) space complexity.**Cons**: Might face integer overflow for very large values of N.

**XOR Approach**:**Pros**: Efficient with O(n) time complexity and O(1) space complexity.**Cons**: Slightly more complex to understand compared to summation approach.

### Edge Cases

**Empty Array**: If the input array is empty, the missing number should be`1`

.**Single Element Missing**: When the array contains only one element, either`1`

(missing`2`

) or`2`

(missing`1`

), handle by checking and returning the missing number.**All Elements Present**: If the array contains all elements from 1 to N without any missing number (should not happen if constraints guarantee a missing number), return a sentinel value like`-1`

.**Duplicated Elements**: This scenario is not considered because the problem constraints specify that all elements are distinct.

### Additional Notes

**Integer Overflow**: For the summation approach, consider the risk of integer overflow when calculating the sum of the first N natural numbers. In practical implementations, ensure the language or environment can handle large integer values.**Data Types**: Choose appropriate data types to handle the range of input values, especially for large N.**Performance Considerations**: While the brute force approach is easy to implement, it is not suitable for large arrays due to its O(n²) time complexity. The hashing and XOR approaches are preferable for large datasets.**In-place Modifications**: For space efficiency, the XOR approach modifies the input array in place. Ensure that this behavior is acceptable in the context of the problem or use case.**Understanding XOR**: The XOR approach leverages the property that`a ^ a = 0`

and`a ^ 0 = a`

. It effectively cancels out duplicate elements and isolates the missing number. This method is both efficient and elegant but requires understanding of bitwise operations.

### Conclusion

Finding the missing number in an array of size N-1 can be achieved using various methods, from simple brute force to optimal XOR-based solutions. Depending on the constraints and requirements, one can choose the most suitable approach.