Find the Duplicate Number (Single Repeated Value in 1..n)

• Problem – an array of n+1 integers in range 1..n has exactly one repeated value; find it.
• Pigeonhole principle – more values than slots guarantees at least one repeat.
• Cyclic Sort – place value v at index v-1; when the home already holds v, that is the duplicate. Mutates the array.
• Floyd's cycle – treat values as next-index pointers, detect the cycle entry. Does not mutate the array.
• Trade-off – Cyclic Sort is simpler but destroys input; Floyd's is read-only but harder to justify.

What is the Find the Duplicate Number problem?

Given an array of n+1 integers where each value is in the range 1 to n, exactly one number is repeated (possibly multiple times). The task is to find the duplicate. Depending on the variant, the array may or may not be modified, and extra space may or may not be used.

package com.bank.dsa;

public class DuplicateFinder {
    // Find the one repeated value
    public int findDuplicate(int[] nums) {
        // implementation below
        return -1;
    }
}

How does the Cyclic Sort approach work?

Place each value v at index v-1 using a while loop. When nums[i] != i + 1, check if nums[i] == nums[nums[i] - 1]. If true, the value is already at its home, so it is the duplicate. Otherwise swap to send it home and continue.

package com.bank.dsa;

public class CyclicSortDuplicate {
    public static int findDuplicate(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            if (nums[i] != i + 1) {
                int home = nums[i] - 1;
                if (nums[i] == nums[home]) {
                    return nums[i]; // duplicate found
                }
                // Swap nums[i] with nums[home]
                int temp = nums[i];
                nums[i] = nums[home];
                nums[home] = temp;
            } else {
                i++;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] apps = {3, 1, 3, 4, 2};
        System.out.println("Duplicate: " + findDuplicate(apps));
    }
}

Duplicate: 3

How does Floyd's cycle approach work?

Treat each value as a pointer: from index i, jump to index nums[i]. Because n+1 values map into 1..n, this functional graph contains a cycle, and the cycle entry is the duplicate. Floyd's two-phase algorithm finds the entry without modifying the array.

package com.bank.dsa;

public class FloydDuplicate {
    public static int findDuplicate(int[] nums) {
        // Phase 1: find meeting point
        int slow = nums[0];
        int fast = nums[nums[0]];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        // Phase 2: find cycle entry
        int finder = 0;
        while (finder != slow) {
            finder = nums[finder];
            slow = nums[slow];
        }
        return finder;
    }

    public static void main(String[] args) {
        int[] apps = {1, 3, 4, 2, 2};
        System.out.println("Duplicate: " + findDuplicate(apps));
    }
}

Duplicate: 2

When should you use each approach?

Use Cyclic Sort when mutation is acceptable and clarity matters. Use Floyd's when the array must stay read-only, which is common in audited banking pipelines where downstream services re-read the original data.

| Approach | Mutates? | Time | Space | Clarity |
|---|---|---|---|---|
| Cyclic Sort | Yes | O(n) | O(1) | Simple |
| Floyd's cycle | No | O(n) | O(1) | Complex |
| HashSet | No | O(n) | O(n) | Simple |
| Binary search (value range) | No | O(n log n) | O(1) | Moderate |

How does the binary search on value range work?

Binary search on the value range 1..n. For a mid value, count how many elements in the array are less than or equal to mid. If the count exceeds mid, the duplicate is in the range 1..mid. Otherwise it is in mid+1..n. This is O(n log n) time and O(1) space.

package com.bank.dsa;

public class BinarySearchDuplicate {
    public static int findDuplicate(int[] nums) {
        int low = 1, high = nums.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            int count = 0;
            for (int num : nums) {
                if (num <= mid) count++;
            }
            if (count > mid) high = mid;
            else low = mid + 1;
        }
        return low;
    }
}

What are edge cases?

Edge cases include the minimum input [1, 1] (duplicate is 1) and an array where the duplicate appears many times like [2, 2, 2, 2, 2]. Both Cyclic Sort and Floyd's handle these correctly.

findDuplicate(new int[]{1, 1});           // 1
findDuplicate(new int[]{2, 2, 2, 2, 2}); // 2

What are common mistakes?

For Cyclic Sort, the mistake is using an equality check on indices instead of values, which misidentifies the duplicate. For Floyd's, the mistake is starting both pointers at 0 instead of at nums[0], which causes the initial comparison to be true immediately.

// Wrong Cyclic Sort: comparing indices
if (i == nums[home]) return i; // wrong

// Correct: comparing values
if (nums[i] == nums[home]) return nums[i];

What should a senior engineer know?

A senior engineer presents both approaches, states the trade-off (mutation vs complexity), and picks based on the constraint. They mention the pigeonhole principle as the theoretical guarantee and know the binary search alternative for when Floyd's is too tricky under time pressure. They also note that if multiple values can repeat, a different approach like counting sort or negation marking is needed.