Training Site

Mindy's Challenge (Take Home Problem)

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

All solutions submitted to this question will now show as 100% even if not the full solution. It will not be marked manually since the contest is over but you are welcome to think about it or send your solution to nzic@nzoi.org.nz.

You will receive 100% for a solution meeting all requirements and 0% otherwise. However, because this is hopefully a challenging problem, I will also award partial marks if you email a solution to nzic@nzoi.org.nz within 72 hours of you finishing the contest. Please only submit solutions which meet all of the constraints. You may wish to screenshot this question for personal reference only. Example input and output is given at the bottom of the page.

The Problem

Mindy has a collection of wonders, each meticulously labelled with a unique identification number starting from 0. However, not only has Mindy given two items the same ID by mistake, little gremlins have changed some IDs to match numbers which have already been assigned a wonder in the collection. What a mess! Luckily, Mindy knows that she has $N$ items in her collection where the maximum assigned ID number is $N-2$. She has asked for your help to track down just one of the duplicate IDs.

Given a list of ID numbers, develop an algorithm to find one of the duplicate IDs given the constraints below. It doesn't matter which duplicate you find if there are multiple to choose from.

1. Use a template* given below to read the ID list/array into memory. This part has no associated points and is not considered as part of your algorithm.
2. Use $O(1)$ extra space**. Explained more below.
3. Do not change the input array referred to as ids. Consider it as read only.
4. You are limited to $O(N)$ accesses of the list/array. Therefore, your algorithm should run in $O(N)$ time.

Warning: this problem is not the same as the Mindy one in Round 2.

*If your language is not available, you may write your own template which does the equivalent.

**Beware that you cannot use data structures such as sets or dictionaries as these allocate extra memory behind the scenes. Some sorting algorithms do this as well. However, you should not require any of these things to solve this problem.

Submitting

You will receive 0% when submitting solutions during the contest (it will show a blue bar with Total Score Pending). Your most recent submission will be marked manually after the contest. Please comment code to explain what you are trying to do.

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.

Input

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

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

Output

One of the duplicate ID numbers on a single line. There will always be at least one duplicate.

Example input/output at the bottom of the page.

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();
}

}
}


Examples

Use these examples to test your code. It's good practice to also think up some of your own test cases.

Input Possible Outputs Input Possible Outputs
10
2
8
1
0
7
6
8
5
4
3

8
10
2
5
1
5
6
4
4
3
0
7

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

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

1