Algorithm


Problem Name: 287. Find the Duplicate Number

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.

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


int findDuplicate(int* nums, int numsSize) {
    int slow, fast;
    
    slow = fast = 0;
    do {
        slow = nums[slow];          // one step
        fast = nums[nums[fast]];    // two steps
    } while (slow != fast);
    
    slow = 0;
    do {
        slow = nums[slow];
        fast = nums[fast];
    } while (slow != fast); // start of the cycle
    
    return slow;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1,3,4,2,2]

Output

x
+
cmd
2

#2 Code Example with Java Programming

Code - Java Programming


class Solution {
  public int findDuplicate(int[] nums) {
    int slow = nums[0];
    int fast = nums[0];
    do {
      slow = nums[slow];
      fast = nums[nums[fast]];
    } while (slow != fast);
    slow = nums[0];
    while (slow != fast) {
      slow = nums[slow];
      fast = nums[fast];
    }
    return fast;
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1,3,4,2,2]

Output

x
+
cmd
2

#3 Code Example with Javascript Programming

Code - Javascript Programming


const findDuplicate = function(nums) {
    const n = nums.length;
    let ans = 0;
    let bit_max = 31;
    while (((n - 1) >> bit_max) == 0) {
      bit_max -= 1;
    }
    for (let bit = 0; bit  < = bit_max; ++bit) {
      let x = 0, y = 0;
      for (let i = 0; i  <  n; ++i) {
        if ((nums[i] & (1 << bit)) != 0) {
          x += 1;
        }
        if (i >= 1 && ((i & (1 << bit)) != 0)) {
          y += 1;
        }
      }
      if (x > y) {
        ans |= 1 << bit;
      }
    }
    return ans;
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [3,1,3,4,2]

Output

x
+
cmd
3

#4 Code Example with Python Programming

Code - Python Programming


class Solution:
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        low, high, mid = 0, len(nums)-1, len(nums)-1 // 2
        while high - low > 1:
            count, mid = 0, (high + low) // 2
            for k in nums:
                if mid < k <= high: count += 1
            if count > high - mid: low = mid
            else: high = mid
        return high
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [3,1,3,4,2]

Output

x
+
cmd
3

#5 Code Example with C# Programming

Code - C# Programming


namespace LeetCode
{
    public class _0287_FindTheDuplicateNumber
    {
        public int FindDuplicate(int[] nums)
        {
            int tortoise = nums[0], hare = nums[0];
            do
            {
                tortoise = nums[tortoise];
                hare = nums[nums[hare]];
            } while (tortoise != hare);

            int ptr1 = nums[0], ptr2 = tortoise;
            while (ptr1 != ptr2)
            {
                ptr1 = nums[ptr1];
                ptr2 = nums[ptr2];
            }

            return ptr1;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1,3,4,2,2]

Output

x
+
cmd
2
Advertisements

Demonstration


Previous
#284 Leetcode Peeking Iterator Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#289 Leetcode Game of Life Solution in C, C++, Java, JavaScript, Python, C# Leetcode