A C# solution to the problem of finding first duplicate - an Google interview question

FindFirstDuplicate.cs

// Original question described in this video
// https://www.youtube.com/watch?v=XSdr_O-XVRQ

public int FindFirstDuplicate(int[] numbers)
{
    for(int i = 0; i < numbers.Length; i++)
    {
        var number = numbers[i];
        if (number < 0)
        {
            number = -number;
        }
        if (numbers[number - 1] < 0) // Found a duplicate
        {
            return number;
        }
        numbers[number - 1] = -numbers[number - 1]; // Mark that this number has appeared once
    }
    return -1;
}

public int FindFirstDuplicate2(int[] numbers)
{
    for(int i = 0; i < length; i++)
    {
        var number = numbers[i] % (numbers.Length + 1);
        if (numbers[number - 1] > (numbers.Length) // Found a duplicate
        {
            return number;
        }
        numbers[number - 1] += (numbers.Length + 1; // Mark that this number has appeared once
    }
    return -1;
}

public int FindFirstDuplicateWithRestoration(int[] numbers)
{
    var firstDuplicate = -1;
    for(int i = 0; i < numbers.Length; i++)
    {
        var number = numbers[i];
        if (number < 0)
        {
            number = -number;
        }
        if (numbers[number - 1] < 0) // Found a duplicate
        {
            firstDuplicate = number;
            break;
        }
        numbers[number - 1] = -numbers[number - 1]; // Mark that this number has appeared once
    }

    // Restore data
    for (int i = 0; i < numbers.Length; i++)
    {
        if (numbers[i] < 0)
        {
            numbers[i] = -numbers[i];
        }
    }
    return firstDuplicate;
}

public int FindFirstDuplicateWithRestoration2(int[] numbers)
{
    int length = numbers.Length;
    var markedIndices = new List<int>();
    var firstDuplicate = -1;
    for(int i = 0; i < length; i++)
    {
        var number = numbers[i];
        if (number < 0)
        {
            number = -number;
        }
        if (numbers[number - 1] > length) // Found a duplicate
        {
            firstDuplicate = number;
            break;
        }
        numbers[number - 1] += length + 1; // Mark that this number has appeared once
        markedIndices.Add(number - 1);
    }

    // Restore marked numbers
    foreach (var index in markedIndices)
    {
        numbers[index] =  -numbers[index];
    }
    return firstDuplicate;
}
// * Summary *

BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18363
Intel Core i7-8705G CPU 3.10GHz (Kaby Lake G), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=3.1.101
  [Host]    : .NET Core 3.1.1 (CoreCLR 4.700.19.60701, CoreFX 4.700.19.60801), X64 RyuJIT
  RyuJitX64 : .NET Core 3.1.1 (CoreCLR 4.700.19.60701, CoreFX 4.700.19.60801), X64 RyuJIT

Job=RyuJitX64  Jit=RyuJit  Platform=X64  


|                              Method |       Mean |    Error |    StdDev |     Median | Gen 0 | Gen 1 | Gen 2 | Allocated |
|------------------------------------ |-----------:|---------:|----------:|-----------:|------:|------:|------:|----------:|
|                         NoDuplicate | 1,262.5 ms | 25.20 ms |  23.57 ms | 1,271.1 ms |     - |     - |     - |         - |
|                DuplicateInTheMiddle |   715.7 ms | 39.64 ms | 116.25 ms |   664.1 ms |     - |     - |     - |         - |
|          NoDuplicateWithRestoration | 2,095.7 ms | 41.53 ms | 111.57 ms | 2,069.6 ms |     - |     - |     - |         - |
| DuplicateInTheMiddleWithRestoration | 1,305.9 ms | 14.65 ms |  13.70 ms | 1,305.1 ms |     - |     - |     - |         - |

// * Warnings *
MultimodalDistribution
  FirstDuplicateFinder.DuplicateInTheMiddle: RyuJitX64       -> It seems that the distribution can have several modes (mValue = 2.92)
  FirstDuplicateFinder.NoDuplicateWithRestoration: RyuJitX64 -> It seems that the distribution is bimodal (mValue = 3.33)

// * Hints *
Outliers
  FirstDuplicateFinder.NoDuplicate: RyuJitX64                -> 1 outlier  was  removed (1.37 s)
  FirstDuplicateFinder.DuplicateInTheMiddle: RyuJitX64       -> 1 outlier  was  removed (1.11 s)
  FirstDuplicateFinder.NoDuplicateWithRestoration: RyuJitX64 -> 11 outliers were removed (2.52 s..3.61 s)

// * Legends *
  Mean      : Arithmetic mean of all measurements
  Error     : Half of 99.9% confidence interval
  StdDev    : Standard deviation of all measurements
  Median    : Value separating the higher half of all measurements (50th percentile)
  Gen 0     : GC Generation 0 collects per 1000 operations
  Gen 1     : GC Generation 1 collects per 1000 operations
  Gen 2     : GC Generation 2 collects per 1000 operations
  Allocated : Allocated memory per single operation (managed only, inclusive, 1KB = 1024B)
  1 ms      : 1 Millisecond (0.001 sec)

// * Diagnostic Output - MemoryDiagnoser *