Interview Bootcamp

0% completed

​

Solution: Find the Duplicate Number

Problem Statement

We are given an unsorted array containing ‘n+1’ numbers taken from the range 1 to ‘n’. The array has only one duplicate but it can be repeated multiple times. Find that duplicate number without using any extra space. You are, however, allowed to modify the input array.

Example 1:

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

Example 2:

Input: [2, 1, 3, 3, 5, 4]
Output: 3

Example 3:

Input: [2, 4, 1, 4, 4]
Output: 4

Constraints:

  • nums.length == n + 1
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= n
  • All the integers in `nums

.....

.....

.....

Like the course? Get enrolled and start learning!
Renat Zamaletdinov

Renat Zamaletdinov

· 2 years ago

What is the idea behind it?

current = arr[arr[slow]]
D

d.psawyer

· 3 years ago

Problem reads:

We are given an unsorted array containing n+1 numbers taken from the range 1 to n. The array has only one duplicate but it can be repeated multiple times. Find that duplicate number without using any extra space. You are, however, allowed to modify the input array.

However, we are supplied 5,5,5,5,5 as a test case. Given that the array is supposed to contain n+1 numbers taken from the range 1 to n If the number 5 is anywhere in the range 1 to n, then the minimum array length must be 6

A

Ada

· 4 years ago

Can't you just return slow value for the similar problem? Since we found that there is a cycle when they meet, then surely the duplicate is the value at the slow position, and thus no use for the find_start method? I just returned the slow value without using find_start and it still passes all the cases mentioned above.

Show 2 replies
V

vetaranto

· 2 years ago

The question (Find the Duplicate Number) should clarify that constant O(1) extra space is allowed given the Python3 solution instantiates a variable (and thus uses extra space).

P

Pete Stenger

· 2 years ago

Solution doesn't work on [3, 1, 3], which is one of the test cases.

Show 2 replies
K

kfaham

· a year ago

test case: [3, 1, 3] is invalid

Length is 3, thus range of each element has to be up to 2 based on the constraints given in the problem other wise the fast & slow pointer approach doesn't work

Show 1 reply
J

Jack Tan

· 8 months ago

<p>Hey Guru,</p><p>The solution in this extra problem seems quite convoluted but it only has minimum explanation. As a mediocre learner myself, I spent a lot of time on it, I was stuck and I felt upset about not fully understanding it.</p><p>From the perspective of good course content design, if the extra problem is important, you should list it as a stand-alone problem and give a detailed explanation, even a video explanation like what NeetCode does; If the extra problem is not important, since the solution is convoluted, it's better to remove it to avoid blocking the learners.</p><p>This is just my two cents. What do you think?</p><p>Thanks!</p>
R

Russell Rogers

· 4 years ago

The hyperlink to the "Start of LinkedList Cycle" actually takes you to the topic on a different website at educative.io instead of this course on designgurus.org.

Show 1 reply
Julius Yudelson

Julius Yudelson

· 3 years ago

The fourth test (first hidden) is [5, 5, 5, 5, 5] but the problem states the array contains numbers 1 through N with N+1 numbers in the array.

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findNumber(self, nums):
    
    def swap(i, j):
      nums[i], nums[j] = nums[j], nums[i]

    for i in range(len(nums)):
      while nums[i] != i + 1 and nums[i] != nums[nums[i] - 1]:
        swap(i, nums[i] - 1)

    return nums[-1]