Find the Duplicate Number LeetCode solution in C++

1
// Please upvote if it helps
2
class Solution {
3
 public:
4
  int findDuplicate(vector<int> &nums) {
5
    int low = 1, high = nums.size() - 1, cnt;
6

7
    while (low <= high) {
8
      int mid = low + (high - low) / 2;
9
      cnt = 0;
10
      // cnt number less than equal to mid
11
      for (int n : nums) {
12
        if (n <= mid) ++cnt;
13
      }
14
      // binary search on left
15
      if (cnt <= mid)
16
        low = mid + 1;
17
      else
18
        // binary search on right
19
        high = mid - 1;
20
    }
21
    return low;
22
  }
23
  // for github repository link go to my profile.
24
};