# Question

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

 287	Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive),
prove that at least one duplicate number must exist.

Assume that there is only one duplicate number, find the duplicate one.

Example 1:

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

Example 2:

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

Note:
You must not modify the array (assume the array is read only). => 不能给原数组排序
You must use only constant, O(1) extra space. => 不能哈希表
Your runtime complexity should be less than O(n^2). => 不能用 brute force
There is only one duplicate number in the array, but it could be repeated more than once.

@tag-array
@tag-binarysearch



# 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.

Java