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

There is only one repeated number in nums, return this&nbsp;repeated&nbsp;number.

You must solve the problem without modifying the array nums&nbsp;and uses only constant extra space.

&nbsp;
Example 1:

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


Example 2:

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


&nbsp;
Constraints:


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


&nbsp;
Follow up:


	How can we prove that at least one duplicate number must exist in nums?
	Can you solve the problem in linear runtime complexity?


class Solution:
    def findDuplicate(self, nums: List[int]) -> int:

        dictx = {}

        for each in nums:
            if each not in dictx:
                dictx[each] = 1
            else:
                return each
class Solution {
    public int findDuplicate(int[] nums) {
        int i = 0; 
         while (i < nums.length) {

            if (nums[i] != i + 1) {
                int correct = nums[i] - 1;
                if (nums[i] != nums[correct]) {
                    swap(nums, i , correct);
                } else {
                    return nums[i];
                }
            } else {
                i++;
            }
        }
        return -1;
    }
     static void swap(int[] arr, int first, int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
   }
                // Please upvote if it helps
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int low = 1, high = nums.size() - 1, cnt;

        while(low <= high)
        {
            int mid = low + (high - low) / 2;
            cnt = 0;
            // cnt number less than equal to mid
            for(int n : nums)
            {
                if(n <= mid)
                    ++cnt;
            }
            // binary search on left
            if(cnt <= mid)
                low = mid + 1;
            else
            // binary search on right
                high = mid - 1;

        }
        return low;
    }
    // for github repository link go to my profile.
};
var findDuplicate = function(nums) {
    let dup = new Map();

    for(let val of nums){
        if(dup.has(val)){
            dup.set(val, dup.get(val) + 1);
            return val;
        }
        else
            dup.set(val, 1);
    }
};
Find the Duplicate Number