Find the Duplicate Number

Problem Statement

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.

To solve this problem, let's begin by understanding the problem statement and reviewing the examples and constraints provided in the question:

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.

Intuition:

Before diving into the solution, let's discuss our approach and how we came up with it. We need to find a duplicate number in an array with some constraints in mind. To do this efficiently, we thought about how to utilize the properties of the given array without modifying it.

Solution:

Our approach involves iterating through the array and marking the elements as negative to indicate that we've seen them before. Here's the algorithm in points:

1. Initialize a variable n to store the length of the nums array.

2. Iterate through the elements in nums.

3. For each element x, calculate the index p as abs(x) - 1.

4. Check if nums[p] is less than 0. If it is, return abs(x) as it indicates a duplicate.

5. Otherwise, set nums[p] to its negative value.

6. If no duplicate is found, return -1.

Code:

public class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length;
        for (int x : nums) {
            int p = Math.abs(x) - 1;
            if (nums[p] < 0) {
                return Math.abs(x);
            } else {
                nums[p] *= -1;
            }
        }
        return -1;
    }
}

And here's the Python version of the code:

class Solution:
    def findDuplicate(self, nums):
        n = len(nums)
        for x in nums:
            p = abs(x) - 1
            if nums[p] < 0:
                return abs(x)
            else:
                nums[p] *= -1
        return -1

Complexity Analysis:

• Time Complexity: O(n) - We iterate through the array once.

• Space Complexity: O(1) - We use constant extra space.

References:

The data structures and algorithms concepts used in this solution include:

• Array manipulation

Connect with me:-

• Twitter

• Github

• LinkedIn