• Find the Duplicate Number

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.
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(n2).
* There is only one duplicate number in the array, but it could be repeated more than once.

Solution:
1. public class Solution {
2. public int findDuplicate(int[] nums) {
3. int a = 0, b = 0;
4. 5. do {
6. a = nums[nums[a]];
7. b = nums[b];
8. } while (a != b);
9. 10. b = 0;
11. 12. while (a != b) {
13. a = nums[a];
14. b = nums[b];
15. }
16. 17. return a;
18. }
19. }