Training Site

# Mindy's Collection

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 100 megabytes
Time limit: 1.0 seconds

Note: scoring has been changed for this problem post-contest. If you get 100% that doesn't mean you would have got 100% in the actual contest, due to manual marking.

Mindy has a collection of wonders, each meticulously labelled with a unique identification number starting from 0. However, somewhere Mindy gave two different items the same ID by mistake! She needs your help to track down the duplicate ID.

Given a list of ID numbers Mindy has allocated so far, tell her which ID is the duplicate. There is guaranteed to be one and only one ID which appears twice in the list, every other ID is unique. If the list is $N$ long, then all IDs must be integers in the range 0 to $N$-2 inclusive.

## Scoring

This problem is a bit different from the others. If you pass all test cases, that does not mean you have the full solution. Additional points for this question will be awarded after the contest is complete (the maximum you can get during the contest is 10%).

1. You must read the list of IDs directly into a list/array first. This part has no associated points and template code is provided below.
2. Once you have a list/array of IDs in your program, you should run your algorithm to find the duplicate.

The score you receive depends on the algorithm you come up with...

• 10% Find the duplicate number by whatever method you want.
• 30% Above but without using any inbuilt/library functions, methods, or data structures (e.g. no sets, dictionaries, .find(), etc).
• 50% Above but using $O(1)$ extra space (excluding the list/array of ID numbers). Explained below.
• 70% Above but limited to $O(N\log N)$ accesses of the ID list/array.
• 100% Above but limited to $O(N)$ accesses of the ID list/array.

Where $N$ is the number of IDs between 10 and 1000.

### Explanation of $O(..)$ Notation

$O(1)$ extra space means that the memory your program requires does not increase as $N$ increases (does not depend on $N$). That effectively means the only list/array you can use is the list/array containing the IDs which is provided in the template.

$O(N)$ accesses mean you have an algorithm which accesses each element in the array a fixed number of times regardless of $N$. For example, your algorithm might need to look at each ID three times on average to obtain an answer. So we are just saying the number of required accesses is proportional to $N$. i.e. you can't use a nested loop if both loops use $N$, you must use a single loop or multiple successive single loops.

$O(N\log N)$ accesses means the number of times you access each element in the array increases with a $\log(N)$ relationship. Usually this happens when your solution divides the problem into smaller problems.

## Submitting

This question will be marked by hand after the contest. If you pass all test cases you can only be guaranteed a minimum of 10%. You may submit solutions to test that your program gets the right answer; however, this is not your final score. It will say Wrong answer for one case but that is just because it hasn't been marked yet so don't worry about it. The last program you submit will be taken as the one you want to be marked on. If you want to leave comments in your program explaining what you are trying to do, you are welcome to do so but it is not required. Good luck :)

## Input

The integer $N$ on a single line followed by $N$ lines each containing one ID.

## Output

The duplicate ID on a single line.

Examples shown below the templates.

## Templates

Python

N = int(input())
ids = []  # A list of Mindy's IDs
for i in range(N):
ids.append(int(input()))



C++

#include <iostream>
int ids[1000];  // An array of Mindy's IDs

int main()
{
int N;
std::cin >> N;
for (int i = 0; i < N; i++) {
std::cin >> ids[i];
}

}


C

#include "stdio.h"
int ids[1000];  // An array of Mindy's IDs

int main(void)
{
int N, i;
scanf("%d", &N);
for (i = 0; i < N; i++) {
scanf("%d", &ids[i]);
}

}


Java

import java.util.Scanner;

public class Filename {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int[] ids = new int[1000];  // An array of Mindy's IDs
for (int i = 0; i < N; i++) {
ids[i] = scanner.nextInt();
}

}
}

• ### Sample Input 1

10
2
8
1
0
7
6
8
5
4
3


### Sample Output 1

8

• ### Sample Input 2

21
14
7
2
6
19
12
1
15
4
8
17
16
10
9
3
13
5
0
1
11
18


### Sample Output 2

1