find-the-duplicate-number

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

Given an array of integers <code>nums</code> containing&nbsp;<code>n + 1</code> integers where each integer is in the range <code>[1, n]</code> inclusive.

There is only one repeated number in <code>nums</code>, return this&nbsp;repeated&nbsp;number.

You must solve the problem without modifying the array <code>nums</code>&nbsp;and using only constant extra space.

&nbsp;
Example 1:

<pre>
Input: nums = [1,3,4,2,2]
Output: 2
</pre>

Example 2:

<pre>
Input: nums = [3,1,3,4,2]
Output: 3
</pre>

Example 3:

<pre>
Input: nums = [3,3,3,3,3]
Output: 3</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>nums.length == n + 1</code></li>
	<li><code>1 &lt;= nums[i] &lt;= n</code></li>
	<li>All the integers in <code>nums</code> appear only once except for precisely one integer which appears two or more times.</li>
</ul>

&nbsp;
Follow up:

<ul>
	<li>How can we prove that at least one duplicate number must exist in <code>nums</code>?</li>
	<li>Can you solve the problem in linear runtime complexity?</li>
</ul>