You are given an array arr[] of size n − 1 that contains distinct integers in…
2024
You are given an array arr[] of size n − 1 that contains distinct integers in the range from 1 to n (inclusive). The array is a permutation of the integers from 1 to n with exactly one element missing. Identify that missing element and print it.
Input format: The first token on standard input is the length of the array, arr.size(). The next arr.size() tokens are the elements of arr[], separated by whitespace.
Output format: Print the single missing integer, followed by a newline.
Examples:
Input: 4 1 2 3 5
Output: 4
Explanation: The length is 4, so arr[] = [1, 2, 3, 5] and n = 5. All the numbers from 1 to 5 are present except 4.
Input: 7 8 2 4 5 3 7 1
Output: 6
Explanation: The length is 7, so arr[] = [8, 2, 4, 5, 3, 7, 1] and n = 8. All the numbers from 1 to 8 are present except 6.
Input: 1 1
Output: 2
Explanation: The length is 1, so arr[] = [1] and n = 2. Only 1 is present, so the missing element is 2.
Constraints:
1 ≤ arr.size() ≤ 106
1 ≤ arr[i] ≤ arr.size() + 1
Attempted by 2 students.
Show answer & explanation
Concept — a permutation of 1 to n from which exactly one value has been removed is recoverable from any aggregate of the complete set that stays invertible when a single element is taken away. Two such aggregates exist: the arithmetic sum, because the total of the first n natural numbers has the closed form n × (n + 1) / 2, and the bitwise XOR, because XOR is its own inverse, so x ^ x = 0 and x ^ 0 = x. Comparing the aggregate of the complete set 1 to n against the aggregate of the given array cancels every value that is present and leaves only the value that was removed.
Applying the sum form to this problem:
Read the length arr.size() from the input, then read that many values. The array stores n − 1 of the n values, so its length fixes n: n = arr.size() + 1.
Compute the total of the complete set with the closed form, expected = n × (n + 1) / 2. This needs no loop.
Compute the total of the given values in one pass, actual = arr[0] + arr[1] + ... + arr[n − 2].
Subtract: missing = expected − actual. Every value that is present contributes once to each total, so it cancels, and only the removed value survives.
Cross-check against the three sample cases:
arr[] = [1, 2, 3, 5] has length 4, so n = 5; expected = 5 × 6 / 2 = 15; actual = 1 + 2 + 3 + 5 = 11; missing = 15 − 11 = 4.
arr[] = [8, 2, 4, 5, 3, 7, 1] has length 7, so n = 8; expected = 8 × 9 / 2 = 36; actual = 8 + 2 + 4 + 5 + 3 + 7 + 1 = 30; missing = 36 − 30 = 6.
arr[] = [1] has length 1, so n = 2; expected = 2 × 3 / 2 = 3; actual = 1; missing = 3 − 1 = 2.
The XOR form reaches the same answer without any large intermediate value:
XOR every integer from 1 to n into a running value x.
XOR every element of the array into a running value y.
Return x ^ y. Each value that is present appears once in x and once in y, so it cancels, and only the removed value remains.
Tracing arr[] = [1, 2, 3, 5]: x = 1 ^ 2 ^ 3 ^ 4 ^ 5 = 1 and y = 1 ^ 2 ^ 3 ^ 5 = 5, so x ^ y = 1 ^ 5 = 4.
Overflow pitfall — when arr.size() reaches 106, the value of n is 106 + 1, the product n × (n + 1) is about 1012 and the expected total is about 5 × 1011. Both exceed the range of a 32-bit signed integer, and widening only the variable that receives the result does not help: in C, C++ and Java the multiplication is already evaluated in the type of its operands, so an int × int product overflows before it is ever assigned. Force the wider type into the multiplication itself — write 1LL * n * (n + 1) / 2 in C or C++ and 1L * n * (n + 1) / 2 in Java, or declare n as long long or long — and accumulate actual in the same 64-bit type. The XOR form avoids the problem for a different reason: XOR never sets a bit above the highest bit of its operands, so when every value is at most 106 + 1, which is below 220, every running XOR also stays below 220 and a 32-bit int is always sufficient. Both forms make a single pass, so both run in O(n) time with O(1) extra space.