The missing number – hints
The task can be solved with a linear search, which is not the best way to solve it. A loop goes through the array and compares the current element with the one we are looking for (an if statement). The loop stops if the number we are looking for is found. In the worst case it goes through all elements from the beginning to the end of the array and finds that the element is not in the array. Use a logical variable (bool, or int in C) to record whether the element we are looking for is in the array or not. For example, this variable can be set to false (0) before the loop. If the element is found, the value of the variable is changed to true (1), and if it is not found until the end of the array, it stays false (0).
You can read more about linear and binary search on the web page: Binary search Advantages and disadvantages:
- Advantages: a simple implementation; it does not need additional data structures.
- Disadvantages: low efficiency, especially for large arrays, because in the worst case all elements of the array are checked.
Practical use
bool found = false;
for (int i = 0; i < arraySize; i++) {
if (array[i] == target) {
found = true;
break;
}
}
Solving the task with a formula
A faster and better way to solve the task is to find the sum of all elements of the array that was read, sumRead, and the sum it would have if no element were missing (sumAll).The difference of these two sums is exactly the element X we are looking for, because: X + sumRead = sumAll
- Computing the sum of all numbers: If the array contains all numbers from 0 to n, their sum is given by the formula:
sumAll = n*(n+1)/2
- Computing the sum of the numbers that were read: Go through the array and add up all the numbers in it:
sumRead = the sum of the numbers in the array that was read
- Finding the missing number: The difference between the sum of all numbers and the sum of the numbers that were read gives the missing number.
For example, if the array is:
0, 1, 2, 4, 5
sumRead = 0+1+2+4+5 = 12
sumAll = 0+1+2+3+4+5 = 15
The number we are looking for is X = sumAll − sumRead = 15 − 12 = 3
