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.

Difficulty: introductory

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)


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

def find_dup(arr):
  l = len(arr)-1
  return sum(arr) - (l * (l+1)) / 2

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