Practice › Arrays
Missing Number
Easy · Arrays · Asked at TCS, Infosys, Wipro, Accenture, Cognizant
The numbers 1 to n are given with exactly one missing (in any order). Find the missing number.
Input
First line: n. Second line: n - 1 distinct integers from 1 to n.
Output
The missing number.
Constraints
- 2 ≤ n ≤ 10^5
Sum formula n(n+1)/2 or XOR both work in O(n).
Example 1
Input
5 1 2 4 5
Output
3
Example 2
Input
2 2
Output
1
Hints
- You know what the sum of 1..n should be.
- Expected sum n(n+1)/2 minus the actual sum is the missing number (or XOR everything).
Approach
The numbers 1..n add up to n(n + 1) / 2. Subtract the sum of the n-1 given numbers and what's left is the missing one. For n = 10^5 the sum is about 5 × 10^9, so use a 64-bit integer. XOR-ing 1..n with all given numbers also works, because every present number cancels itself.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n, x, sum = 0;
cin >> n;
for (int i = 0; i < n - 1; i++) {
cin >> x;
sum += x;
}
cout << n * (n + 1) / 2 - sum << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
print(n * (n + 1) // 2 - sum(data[1:n]))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong(), sum = 0;
for (int i = 0; i < n - 1; i++) sum += sc.nextLong();
System.out.println(n * (n + 1) / 2 - sum);
}
}