# Question

Formatted question description: https://leetcode.ca/all/287.html

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 <= 105
• 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.

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

# Algorithm

Using the binary search method, search in the interval [1, n], first find the midpoint mid, then traverse the entire array, count all the numbers less than or equal to mid,

• If the number is less than or equal to mid, the repeated value is between [mid+1, n],
• On the contrary, the repeated value should be between [1, mid-1], Until the search is completed, low index then is the repeated value we require.

### Bit

For each digit, the number of 1s in this digit in all numbers from 0 to n-1 should be fixed. If there are more 1s in this digit in all numbers in the nums array, it means that the this 1 is in duplicated number. We can reproduce the repeated number by adding up all the 1 bits of the repeated number.

# Code

• import java.util.Arrays;

public class Find_the_Duplicate_Number {

class Solution_bit {
public int findDuplicate(int[] nums) {
int res = 0, len = nums.length;
for (int i = 0; i < 32; ++i) {
int bit = (1 << i), cnt1 = 0, cnt2 = 0;
for (int k = 0; k < len; ++k) { // len is actually n+1
if ((k & bit) > 0) ++cnt1; // 1s count with no duplicate
if ((nums[k] & bit) > 0) ++cnt2; // 1s count with no duplicate
}
if (cnt2 > cnt1) res += bit;
}
return res;

}
}

class Solution {
public int findDuplicate(int[] nums) {
int left = 1, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2, cnt = 0;
for (int num : nums) {
if (num <= mid) ++cnt;
}
// eg. 1,1,1,1,1,1,1,2
// eg. 1,2,2,2,2,2,2,2
if (cnt <= mid) left = mid + 1;
else right = mid;
}
return right;
}
}

class Solution_sort {
public int findDuplicate(int[] nums) {
Arrays.sort(nums);
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i-1]) {
return nums[i];
}
}

return -1;
}
}
}

############

class Solution {
public int findDuplicate(int[] nums) {
int left = 1, right = nums.length - 1;
while (left < right) {
int mid = (left + right) >> 1;
int cnt = 0;
for (int v : nums) {
if (v <= mid) {
++cnt;
}
}
if (cnt > mid) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}

• // OJ: https://leetcode.com/problems/find-the-duplicate-number/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
int findDuplicate(vector<int>& A) {
int L = 1, R = A.size() - 1;
while (L < R) {
int M = (L + R) / 2, cnt = 0;
for (int n : A) cnt += n <= M;
if (cnt <= M) L = M + 1;
else R = M;
}
return L;
}
};

• class Solution:
def findDuplicate(self, nums: List[int]) -> int:
left, right = 1, len(nums) - 1
while left < right:
mid = (left + right) >> 1
cnt = sum(v <= mid for v in nums)
if cnt > mid:
right = mid
else:
left = mid + 1
return left

############

class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums) - 1
start, end = 1, n
while start + 1 < end:
mid = start + (end - start) / 2
count = 0
for num in nums:
if num < mid:
count += 1
if count >= mid:
end = mid
else:
start = mid
if nums.count(start) > nums.count(end):
return start
return end


• func findDuplicate(nums []int) int {
left, right := 1, len(nums)-1
for left < right {
mid := (left + right) >> 1
cnt := 0
for _, v := range nums {
if v <= mid {
cnt++
}
}
if cnt > mid {
right = mid
} else {
left = mid + 1
}
}
return left
}

• function findDuplicate(nums: number[]): number {
let left = 1,
right = nums.length - 1;
while (left < right) {
const mid = (left + right) >> 1;
let cnt = 0;
for (let v of nums) {
if (v <= mid) {
++cnt;
}
}
if (cnt > mid) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}


• /**
* @param {number[]} nums
* @return {number}
*/
var findDuplicate = function (nums) {
let left = 1,
right = nums.length - 1;
while (left < right) {
const mid = (left + right) >> 1;
let cnt = 0;
for (let v of nums) {
if (v <= mid) {
++cnt;
}
}
if (cnt > mid) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};


• impl Solution {
pub fn find_duplicate(nums: Vec<i32>) -> i32 {
let mut left = 0;
let mut right = nums.len() - 1;

while left < right {
let mid = (left + right) >> 1;
let cnt = nums
.iter()
.filter(|x| **x <= mid as i32)
.count();
if cnt > mid {
right = mid;
} else  {
left = mid + 1;
}
}

left as i32
}
}