## Friday, October 2, 2015

### [Leetcode] Find the Duplicate Number, Solution

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:
1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than `O(n2)`.
4. There is only one duplicate number in the array, but it could be repeated more than once.

[Thoughts]

[Code]
``````1:  class Solution {
2:  public:
3:    int findDuplicate(vector<int>& nums) {
4:      int length = nums.size();
5:      for(int i =0; i< length; i++) {
6:        if(nums[i] == i+1) {
7:          continue;
8:        }
9:        int oldIndex = i;
10:        int newIndex = nums[i]-1;
11:        while(nums[oldIndex] != oldIndex +1 ) {
12:          if(nums[oldIndex] == nums[newIndex] ) {
13:            return nums[oldIndex];
14:          }
15:          int temp = nums[newIndex];
16:          nums[newIndex] = nums[oldIndex];
17:          nums[oldIndex] = temp;
18:          newIndex = nums[oldIndex] -1;
19:        }
20:      }
21:    }
22:  };
``````

github: https://github.com/codingtmd/leetcode/blob/master/src/Find_the_Duplicate_Number.cpp