findDuplicate.cpp

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

int solve1(int N, std::vector<int> a){
    sort(a.begin(), a.end());
    for(int i = 0; i < N+1; i++){
        if(a[i] == a[i+1]) return a[i];
    }
    return -1;
}

int solve2(int N, std::vector<int> a){
    unordered_map<int, int> d;

    for(int i = 0; i < N+1; i++){
        if (d.find(a[i]) == d.end()) return a[i];
        d[a[i]] = 0ll;
    }
    return -1;
}

int solve3(int N, std::vector<int> a){
    int tortoise;
    int hare;
    tortoise = a[0];
    hare = a[a[0]];
    while (tortoise != hare)
    {
        tortoise = a[tortoise];
        hare = a[a[hare]];
    }
    hare = 0;
    while (tortoise != hare)
    {
        tortoise = a[tortoise];
        hare = a[hare];
    }
    return hare;
}


int main(int argc, char **argv){
    int type=1;
    if (argc > 1){
        type = atoi(argv[1]);
    }

    int N;
    scanf("%d",&N);
    std::vector<int> a(N+1);
    for(int i = 0 ; i < N+1 ; i++){
        scanf("%d",&a[i]);
    }
    switch (type) {
        case 1:
            cout << "algo1" << endl;
            cout << solve1(N, std::move(a));
            break;
        case 2:
            cout << "algo2" << endl;
            cout << solve2(N, std::move(a));
            break;
        case 3:
            cout << "algo3" << endl;
            cout << solve3(N, std::move(a));
            break;
        default:
            break;
    }
    return 0;
}