Find the duplicate number

Array Two Pointers Binary Search Bit Manipulation

64.0% acceptance

Jan 12, 2026

25356

5760

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn find_duplicate(nums: Vec<i32>) -> i32 {
    let mut slow = nums[0];
    let mut fast = nums[0];
    
    loop {
      slow = nums[slow as usize];
      fast = nums[nums[fast as usize] as usize];
      if slow == fast {
        break;
      }
    }
    
    slow = nums[0];
    while slow != fast {
      slow = nums[slow as usize];
      fast = nums[fast as usize];
    }
    
    slow
  }
}