287. Find the Duplicate Number

Problem

Tags: Array, Two Pointers, Binary Search, Bit Manipulation

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 uses only constant extra space.

Example 1:

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

Example 2:

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

Constraints:

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

Follow up:

• How can we prove that at least one duplicate number must exist in nums?
• Can you solve the problem in linear runtime complexity?

Code

C

// 287. Find the Duplicate Number (2/4/54210)
// Runtime: 140 ms (42.57%) Memory: 14.42 MB (9.69%) 

int comp (int* a, int* b) {
    return *a - *b;
}

int findDuplicate (int nums[], int nums_size) {
    qsort(nums, nums_size, sizeof(int), &comp);
    
    for (int i = 0; i < nums_size - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            return nums[i];
        }
    }
    
    return 0;
}