Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Arrays

Find the Duplicate Number

Medium · Arrays · Asked at Amazon, Microsoft, Google, Bloomberg

The array has n + 1 integers, each in the range [1, n]. Exactly one value is repeated (possibly more than twice). Print it — ideally without modifying the array and with O(1) extra space.

Input

First line: n + 1 (the array length). Second line: the array.

Output

The repeated value.

Constraints

Treat i → a[i] as a linked list: the duplicate is where the cycle starts (Floyd's tortoise and hare).

Example 1

Input

5
1 3 4 2 2

Output

2

Example 2

Input

5
3 1 3 4 2

Output

3

Hints

  1. Think of each index i as a node with an edge to a[i]. Because some value repeats, two nodes point to the same node — a cycle with an "entrance".
  2. Floyd's algorithm: move slow by one step and fast by two until they meet, then restart one pointer from the start; where they meet again is the duplicate.

Approach

Values are in [1, n] and there are n + 1 of them, so i → a[i] never leaves the array and must eventually loop. Index 0 has no incoming edge, so starting there we walk into the cycle; the node where the cycle begins has two incoming edges — the duplicated value. Phase 1: slow = a[slow], fast = a[a[fast]] until they meet. Phase 2: reset slow = 0 and move both one step at a time; they meet at the cycle entrance. O(1) extra space, array untouched.

Complexity: O(n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a) cin >> x;
    int slow = 0, fast = 0;
    do {
        slow = a[slow];
        fast = a[a[fast]];
    } while (slow != fast);
    slow = 0;
    while (slow != fast) {
        slow = a[slow];
        fast = a[fast];
    }
    cout << slow << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
a = data[1:]
slow = fast = 0
while True:
    slow = a[slow]
    fast = a[a[fast]]
    if slow == fast:
        break
slow = 0
while slow != fast:
    slow, fast = a[slow], a[fast]
print(slow)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        int slow = 0, fast = 0;
        do {
            slow = a[slow];
            fast = a[a[fast]];
        } while (slow != fast);
        slow = 0;
        while (slow != fast) {
            slow = a[slow];
            fast = a[fast];
        }
        System.out.println(slow);
    }
}

Solve Find the Duplicate Number online · All practice problems