[LeetCode] Find the Duplicate Number

 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 };

 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 };