Spin-off of this kata, here you will have to figure out an efficient strategy to solve the problem of finding the sole duplicate number among an unsorted array/list of numbers starting from 1 up to n.

Hints: a solution in linear time can be found; using the most intuitive ones to search for duplicates that can run in O(n²) time won't work.

Source: codewars | Difficulty: EASY
Tags: Data structures

Starter code: def find_dup(arr):
	

Solutions:
def find_dup(arr):
	return sum(arr) - sum(range(1, max(arr) + 1))


def find_dup(arr):
	seen = set()
	for a in arr:
		if a in seen:
			return a
		seen.add(a)


find_dup = lambda arr: sum(arr) - len(arr) * (len(arr) - 1) / 2


from collections import Counter

def find_dup(lst):
	return Counter(lst).most_common()[0][0]


def find_dup(arr):
	memo = set()
	return next((x for x in arr if x in memo or memo.add(x)))


def find_dup(xs):
	found = set()
	for x in xs:
		if x in found:
			return x
		found.add(x)


def find_dup(arr):
	return sum(arr, (1 - len(arr)) * len(arr) / 2)