Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. You know what the sum of 1..n should be.
  2. 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);
    }
}

Solve Missing Number online · All practice problems