Contains duplicate

Easy

2000 ms limit256 MB memoryArrays Hash sets

Stuck?

Show a hint

Keep a set of what you have already seen. If the current number is in it, you are done.

The ideas behind this problem

Maps and sets in everyday code Hash tables: how a lookup can skip the search Trading memory for time with a hash map Arrays, and allocating memory Vectors and the standard algorithms Arrays and ArrayList Lists and tuples

Next in this lesson

Valid anagram

Given a list of numbers, say whether any number appears more than once.

Worked example#

For [1, 2, 3, 1], walk through keeping a note of everything seen:

number	seen before?	notes so far
1	no	1
2	no	1, 2
3	no	1, 2, 3
1	yes	stop, the answer is true

For [1, 2, 3, 4] you reach the end without ever seeing a repeat, so the answer is false.

Checking every pair would work, but on a list of 100000 numbers that is five billion comparisons. Remembering what you have seen turns it into one pass.

Constraints#

1 <= n <= 100000
-10^9 <= nums[i] <= 10^9

Input

nums is a count then that many integers.

Output

true or false.

Examples

Input

4
1 2 3 1

Output

true

The 1 at the end has been seen already.

Input

4
1 2 3 4

Output

false

Every number is different, so the answer is false.

Input

1
5

Output

false

A single number cannot repeat.

Something wrong with this problem? Report an issue

Ready to try it

Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.

Create a free account Sign in

Free, and it stays free. No card.