[LeetCode] Find the Duplicate Number

There are mainly two solutions to solve this problem.

The first one is very clever, using the idea of cycle detection, and runs in O(n) time. You may refer to this post, whose code is rewritten below.

 1 class Solution {
 2 public:
 3     int findDuplicate(vector<int>& nums) {
 4         int n = nums.size(), slow = n - 1, fast = n - 1;
 5         do {
 6             slow = nums[slow] - 1;
 7             fast = nums[nums[fast] - 1] - 1;
 8         } while (slow != fast);
 9         fast = n - 1; 
10         do {
11             slow = nums[slow] - 1;
12             fast = nums[fast] - 1;
13         } while (slow != fast);
14         return slow + 1;
15     }
16 };

The second one uses binary search to search for possible numbers in ranges [1, n] and eliminate one half at each time. You may refer to this nice post for a good explanation. The code is rewritten below in C++.

 1 class Solution {
 2 public:
 3     int findDuplicate(vector<int>& nums) {
 4         int n = nums.size(), l = 1, r = n - 1;
 5         while (l < r) {
 6             int m = l + ((r - l) >> 1);
 7             int cnt = notGreaterThan(nums, m);
 8             if (cnt <= m) l = m + 1;
 9             else r = m;
10         } 
11         return l;
12     }
13 private:
14     int notGreaterThan(vector<int>& nums, int target) {
15         int cnt = 0;
16         for (int num : nums)
17             if (num <= target)
18                 cnt++;
19         return cnt;
20     }
21 };