Missing House Numbers
National Olympiad — Municipal round (2023 season)
Submission name: street.cpp
Problem summary
Odd house numbers on one side of a street run from 1 through the largest odd number; even numbers on the other run from 2 through the largest even number. Some numbers were erased, but neither largest number was erased. Find how many odd and even numbers were erased.
Input
N, then N surviving numbers: increasing odds followed by increasing evens. Both parities occur.
Output
The missing odd count and missing even count.
Constraints
1 < N < 999; surviving numbers are in [1,10000].
Worked example
An independently prepared example for this explanation.
Input
6 5 9 4 6 10 12
Output
3 2
Solution analysis
- The largest surviving number of each parity is also the original last house number on that side. Thus it determines how many houses originally existed.
- There are (largestOdd+1)/2 odd houses and largestEven/2 even houses. Count how many input values have each parity, then subtract these counts.
- In the sample the odd side ends at 9, so it has five houses but only 5 and 9 survive: three are missing. The even side ends at 12, so six houses minus four survivors leaves two.
Why it works
The unerased endpoints determine the complete original parity sequences. Subtracting the surviving members from their sizes counts exactly the erased members.
Watch out. Use the largest number separately for each parity; the two sides can have different lengths.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int oddCount = 0, evenCount = 0, largestOdd = 0, largestEven = 0;
for (int i = 0; i < n; i++) {
int value;
cin >> value;
if (value % 2 == 1) {
oddCount++;
largestOdd = max(largestOdd, value);
} else {
evenCount++;
largestEven = max(largestEven, value);
}
}
// Uncrossed endpoints reveal the original number of houses on each side.
cout << (largestOdd + 1) / 2 - oddCount << ' ' << largestEven / 2 - evenCount << '\n';
}