## Given problem

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?

## Using Cyclic Sort

Currently, we will use cyclic sort to solve this issue.

``````class Solution {
public int findDuplicate(int[] nums) {
int size = nums.length;
int start = 0;

while (start < size) {
int current = nums[start] - 1;

if (nums[start] != nums[current]) {
swap(nums, start, current);
} else {
++start;
}
}

for (int i = 0; i < size; ++i) {
if (nums[i] != i + 1) {
return nums[i];
}
}

return size;
}

private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
``````

But we can improve it by only need to check on the first loop, instead of using a new loop.

``````class Solution {
public int findDuplicate(int[] nums) {
int size = nums.length;
int start = 0;

while (start < size) {
int current = nums[start] - 1;

if (nums[start] != start + 1) {
if (nums[start] != nums[current]) {
swap(nums, start, current);
} else {
return nums[start];
}
} else {
++start;
}
}

return -1;
}

private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
``````

The complexity of this solution:

• Time complexity: O(n)
• Space complexity: O(1)

## Using marker points

In this solution, we will mark the value at `nums[i] - 1` position as its negative value. If we encounter the duplicated element, the value at `nums[i] - 1` position will be less than 0. Then, we can break our loop, simply because there’s only one duplicated element from our problem.

Below is the source code of this solution:

``````class Solution {
public int findDuplicate(int[] nums) {
int duplicate = -1;

for (int i = 0; i < nums.length; ++i) {
int val = (nums[i] < 0 ? -nums[i] : nums[i]);
if (nums[val - 1] >= 0) {
nums[val - 1] = -nums[val - 1];
} else {
duplicate = val;
break;
}
}

for (int i = 0; i < nums.length; ++i) {
if (nums[i] < 0) {
nums[i] = -nums[i];
}
}

return duplicate;
}
}
``````

The complexity of this solution:

• Time complexity: O(n)
• Space complexity: O(1)

## Wrapping up

Refer:

287. Find the Duplicate Number