Skip to the content ForoHackers
Log inJoin

Puzzle: find the duplicate in an array of n+1 numbers

AlgorithmsCompetitive programmingPuzzles
#1139 · off_by_two · · Report

An array holds n + 1 integers, each between 1 and n. By the pigeonhole principle at least one value appears twice. Assume exactly one value is duplicated (it may appear more than twice).

Find it with these constraints:

  • O(1) extra space.
  • Do not modify the array.
  • Faster than O(n^2) time.

Example: [3, 1, 3, 4, 2] has n = 4, and the answer is 3.

Sorting is out (it modifies the array or needs extra space). A hash set is out (extra space). Think about what the values mean as indices.

Spoilers in replies, please. Bonus for a proof that your method terminates.

#1880 · SiestaDeAlgoritmos · · Report

Spoiler. Trata cada valor como un puntero: la posición i apunta a la posición a[i]. Como hay n + 1 posiciones y los valores van de 1 a n, el "camino" que empieza en la posición 0 nunca sale del array y tiene que acabar en un ciclo. La entrada del ciclo es el valor duplicado, porque dos posiciones distintas apuntan a ella. Se encuentra con la liebre y la tortuga de Floyd.

#1881 · hexdump_hermit · · Report

Spoiler, code:

int find_dup(const int *a, int n) {
    int slow = a[0], fast = a[a[0]];
    while (slow != fast) { slow = a[slow]; fast = a[a[fast]]; }
    slow = 0;
    while (slow != fast) { slow = a[slow]; fast = a[fast]; }
    return slow;
}

First loop finds a meeting point inside the cycle. Second loop starts one pointer from the head and moves both at the same speed: they meet exactly at the cycle entrance.

#1882 · off_by_two · · Report

Both right. Note why value 0 is never a target: it is not in 1..n, so position 0 is never entered by an edge, which is why starting there is safe. Bonus bonus: a binary search on the value range also works in O(n log n) with O(1) space, by counting how many elements are <= mid.

#1883 · quiet_quine · · Report

Short version in Python, for the golfers:

def dup(a):
    s = f = 0
    while True:
        s, f = a[s], a[a[f]]
        if s == f: break
    s = 0
    while s != f: s, f = a[s], a[f]
    return s

Log in or join to reply.