Find the Duplicate Number - Practice Coding Problems

Find the Duplicate Number - Problem

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and using only constant extra space.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,3,4,3,2]

› Output: 3

💡 Note: The number 3 appears at indices 1 and 3, making it the duplicate number

Example 2 — Duplicate at End

$ Input: nums = [3,1,3,4,2]

› Output: 3

💡 Note: The number 3 appears at indices 0 and 2, so 3 is the duplicate

Example 3 — Minimum Size

$ Input: nums = [1,1]

› Output: 1

💡 Note: With only 2 elements in range [1,1], the duplicate must be 1

Constraints

1 ≤ n ≤ 10⁵
nums.length == n + 1
1 ≤ nums[i] ≤ n
All integers in nums appear only once except for precisely one integer which appears two or more times.

Visualization

Tap to expand

Understanding the Visualization

Input

Array with n+1 integers, one appears twice

Process

Find the number that appears more than once

Output

Return the duplicate number

Key Takeaway

🎯 Key Insight: Transform into cycle detection by treating array values as pointers to indices

Asked in

M Microsoft 45 🍎 Apple 38 a Amazon 35 G Google 32

The key insight is to recognize this as a cycle detection problem by treating array values as pointers. The optimal approach uses Floyd's Cycle Detection Algorithm (Tortoise and Hare) to find the duplicate in O(n) time with O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer Space	O(n log n)	O(1)	Binary search on possible duplicate values, counting elements ≤ mid
Brute Force - Check All Pairs	O(n²)	O(1)	Compare every element with every other element to find the duplicate
Floyd's Cycle Detection (Tortoise and Hare)	O(n)	O(1)	Treat array as linked list where nums[i] points to index nums[i], use cycle detection

Binary Search on Answer Space — Algorithm Steps

Set search range [1, n]
For mid value, count elements ≤ mid
If count > mid, duplicate is in left half, else right half

Visualization

Tap to expand

Step-by-Step Walkthrough

Range

Search in range [1, n]

Count

Count elements ≤ mid

Narrow

Adjust search based on count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    int left = 1, right = numsSize - 1;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        int count = 0;
        for (int i = 0; i < numsSize; i++) {
            if (nums[i] <= mid) count++;
        }
        
        if (count > mid) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int count = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[count++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(nums, count));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Binary search runs log n iterations, each iteration counts n elements

⚡ Linearithmic

Space Complexity

O(1)

Only using constant variables for search bounds and counters

✓ Linear Space

78.0K Views

High Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer Space — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler