_287. Find the Duplicate Number.md

287. Find the Duplicate Number

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 26, 2024

Last updated : June 26, 2024

---

Related Topics : Array, Two Pointers, Binary Search, Bit Manipulation

Acceptance Rate : 62.14 %

---

Solutions

• m287 One of my favs.c

C

m287 One of my favs.c

/**
 * Thought process
 * Each value will point to another index, and that
 * to another and another 
 * 
 * We're given values [1, n] inclusive of length n+1 so
 * XORing should be (1^2^...^n) ^ repeatVal
 * 
 */


int findDuplicate(int* nums, int numsSize) {
    int fast = nums[0];
    int slow = nums[0];

    do {
        fast = nums[nums[fast]];
        slow = nums[slow];
    } while (fast != slow);

    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }

    return fast;

}