Skip to content
Katabench
Try free

Find the Duplicate Number

Medium About 25 min Free, no account needed

Find the one repeated value in an array of n+1 numbers from 1..n, without allocating a set to do it.

The brief

Given an array nums of n + 1 integers where each value is in the range 1..n, exactly one value is repeated (it may appear more than twice). Return that repeated value.

  • Do not modify the input array.

The performance bar

The obvious approach compares every pair of elements, O(n²). The hidden test uses 200,001 numbers whose duplicate sits far from the start, so that is too slow.

The memory bar

The obvious fix, remembering every value in a HashSet<int>, is fast but allocates megabytes of buckets and entries. The hidden test also measures the bytes your code allocates and fails anything over a strict 16 KB budget, so a set, a bool[] of seen flags, or a sorted copy all blow it. The values being confined to 1..n is the lever: it lets you find the repeat in O(n) time with a fixed handful of variables, and the input left untouched.

Starter code

C#
using System;

public class Solution
{
    // TODO: return the value that appears more than once in nums.
    public int FindDuplicate(int[] nums)
    {
        throw new NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Two pointers
Walk a sorted or symmetric sequence from both ends, or fast and slow, instead of checking every pair.

Do these first

Related katas