Find the Duplicate Number

Question

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

My solution:

def findDuplicate(nums):
    slow = fast = finder = 0
    while fast is not None:
    
    
        slow = nums[slow]
        fast = nums[nums[fast]]
    
        if fast is slow:
            return slow
       
   return False

nums = [1,2,2,3,4]
print findDuplicate(nums)

My above solution works and gives me o/p 2 but it doesn't work for every input for example it doesn't work for [11,15,17,17,14] or [3,1,2,6,2,3] and gives me error IndexError: list index out of range. I am not able to find patterns and am not able to track down the exact problem. Also tried to change my while condition:

while fast is not None and nums[nums[fast]] is not None:

your help will be greatly appreciated! Thank you.

Answer 1

Since the numbers are between 1 and n and you have been told there is only one duplicate, you can use difference between the sum of the numbers in the array and the sum of numbers from 1 to n to get the duplicate.

def findDuplicate(l):
    n = len(l) - 1                     # Get n as length of list - 1
    return sum(l) - (n * (n + 1) / 2)  # n*(n+1)/2 is the sum of integers from 1 to n

So the duplicate is the sum of the list - n*(n+1)/2

Of course, this doesn't generalize to finding duplicates for any list. For that case, you need to use @Jalepeno112 's answer.

Answer 2

The fact that the first one works is a fluke. Let's look at what it does on the first pass.

nums = [1,2,2,3,4]
# slow starts as index 0.  So now, you've reassigned slow to be nums[0] which is 1.
# so slow equals 1
slow = nums[slow]

# now you are saying that fast equals nums[nums[0]].  
# nums[0] is 1.  nums[1] is 2
# so fast = 2        
fast = nums[nums[fast]]

On the next pass, slow will be nums[1] which is 2. fast will be nums[nums[2]] which is nums[2] which is 2. At this point slow and fast are equal.

In your second example, you are getting an IndexError because of fast = nums[nums[fast]] If the value at nums[fast] is not a valid index, then this code will fail. Specifically in the second example, nums[0] is 11. nums doesn't have an element at index 11, so you get an error.

What you really want to be doing is performing a nested for loop on the array:

# range(0,len(nums)-1) will give a list of numbers from [0, to the length of nums-1)
# range(1, len(nums)) does the same, 
# except it will start at 1 more than i is currently at (the next element in the array).  
# So it's range is recomputed on each outer loop to be [i+1, length of nums)
for i in range(0,len(nums)-1):
   for j in range(i+1,len(nums)):
       # if we find a matching element, return it
       if nums[i] == nums[j]:
           return nums[i]
# if we don't find anything return False
return False 

There are likely other more Pythonic ways to achieve this, but that wasn't your original question.

Answer 3

first you must ensure all numbers in list satisfy your constrains.

to find duplicated numbers in a list Use Counter in collections it will return each number and number of occurrence example :

>>> from collections import Counter
>>> l=Counter([11,15,17,17,14])
>>> l
Counter({17: 2, 11: 1, 14: 1, 15: 1})

to get the most common one use :

>>> l.most_common(n=1)
[(17, 2)]

where n is the number most common numbers you want to get

Answer 4

def duplicates(num_list):
    if type(num_list) is not list:
        print('No list provided')
            return
    if len(num_list) is 0 or len(num_list) is 1:
        print('No duplicates')
            return
    for index,numA in enumerate(num_list):
        num_len = len(num_list)
            for indexB in range(index+1, num_len):
                if numA == num_list[indexB]:
                    print('Duplicate Number:'+str(numA))
                        return
duplicates([11,15,17,17,14])
duplicates([3,1,2,6,2,3])
duplicates([])
duplicates([5])

Answer 5

l=[]
n= int(input("the number of digit is :"))
l=[0 for k in range(n)]
for j in range(0,n):
  l[j]=int(input("the component is"))
print(l)
b=0;  c=0
for i in range(n):
 if l[i]== l[n-1-i]:
    b=1;c=i
if b==1:
 print("duplicate found! it is",l[c])
elif b==0:
 print("no duplicate")

Answer 6

The answer is unfinished. It tries to convert the array to a linked list. So far it found where the slow pointer and fast pointer met, but this is the halfway solution. To get the solution, we need to initialize another pointer from the beginning of the linked list and walk towards each other. When they meet, that point is the where cycle is detected, in our question it is where the single point is:

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow,fast=0,0
        while True:
            slow=nums[slow]
            fast=nums[nums[fast]]
            if slow==fast:
                break
        slow2=0
        while True:
            slow2=nums[slow2]
            slow=nums[slow]
            if slow==slow2:
                return slow2