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: 2Example 2:
Input: nums = [3,1,3,4,2]
Output: 3Example 3:
Input: nums = [1,1]
Output: 1Example 4:
Input: nums = [1,1,2]
Output: 1Constraints:
1 <= n <= 105nums.length == n + 11 <= nums[i] <= n- All the integers in
numsappear only once except for precisely one integer which appears two or more times
Some approaches that would solve the problem , but against the defined constraints
Approach 1 :
Sorting
Sort the array and while traversing the array , see if a[i]==a[i+1]
if so, that is the duplicate element
Time: O(nlgn)
Space: O(1)
Note: This is against the constraint that array here is modified while traversing
Approach 2:
Hashing
While traversing add the elements already visited to a hash set, and see for upcoming element, whether the element is present in the hash set or not.
Time: O(n)
Space: O(n)
Note: This is against the constraint that as extra space is used here.
Approach 3
Marking value at an index position to negative(flagging)
As all the elements in the given array is 1 to n , we can use the negative flagging technique.
Essentially, what we, do here is for all the numbers we assign an index position for value 1, we assign index position 0, for value 2 , assign index position 1 and so on.
As we traverse the array say let’s we are at ‘i’ th position and value at ‘i’ is nums[i] , then the value at nums[i]-1 , which is the assumed index position of value nums[i], is made to negative . And this would ensure that if a number repeats and the second time we see that number, then the corresponding value at its index position nums[i]-1 would be already been made to negative . Thus we return the answer as nums[i].
Solution
def findDuplicate(self, nums):
for i in range(len(nums)):
index=abs(nums[i])-1
if(nums[index]>0):
nums[index]*=-1
else:
return abs(nums[i])Time: O(n)
Space: O(1)
Note: This is against the constraint as we have modified the array .
Approach 4 and Approach 5(Array as HashMap (Recursion& Iterative))
https://leetcode.com/problems/find-the-duplicate-number/solution/
Approach 6 :
Binary search
One point to note is , that the minimum count of the duplicate number in the array is 2 , according to the pigeon hole principle.
Here as we move from values 1 to the n, for all values greater than or equal to the duplicating value , the number of values less than or equal to these values are greater than the their actual values. For all values from 1 to n , which is less than the duplicate value ,the count of numbers less than or equal to that number is always less than or equal to their the value. So this count of all numbers less than a particular number is therefore monotonically increasing sequence , therefore is a boon to use the binary search method.
Our required answer would be that number ,which is the first element in the sequence from 1 to n , having the number of terms less than or equal to this number , greater than the number itself .
The same idea can also be implemented without using the binary search method and it would cost you o f O(n²). This idea is by traversing the array and returning that element which has number of counts of values less or equal to it is the least.
class Solution(object):
def findDuplicate(self, nums):
low=1
high=len(nums)-1
def counter(nums,n):
cnt=0
for i in range(len(nums)):
if nums[i]<=n:
cnt+=1
return cnt
min_count=float('inf')
while(low<=high):
mid=(low+high)//2
counts=counter(nums,mid)
if counts>mid and min_count>=counts:
#print("/",[mid])
min_count=counts
val=mid
if(counts<=mid):
low=mid+1
else:
high=mid-1
return valTime: O(nlgn)
For each number currently on checking , we should traverse the entire array in O(n) time , that is to find the exact number lgn steps are needed and for each of those steps we need complete traversal of the array in O(n) time.
Space: O(1)
Approach 7:
Using bitmask
One way to think this, least number of times the one and only duplicate number appearing in the array is 2 , based on the pigeonhole principle. And if we find the number of 1’s in each of the bit position places, which is sum of 1’s in that bit position for all numbers from 1 to n , let it be denoted by “range_cnt”, and also find the number of 1’s for each bit position for all the number present in the array, let it be denoted by, nums_cnt. Then the duplicate number will be represented by a 1 in those bit position where the difference , nums_cnt — range_cnt is >0.
def findDuplicate(self, nums):
size=(len(nums)-1).bit_length()
val=0
for i in range(size):
mask=1<<i
nums_cnt=0
range_cnt=0
for j in nums:
if j&mask!=0:
nums_cnt+=1
for k in range(1,len(nums)):
if k&mask!=0:
range_cnt+=1
if(nums_cnt-range_cnt>0):
val|=mask
return valTime :O(nlgn)
Space: O(1)
Approach 8:
Using Floyd’s Cycle Detection algorithm
If you closely observe the problem , this is actually the application of detecting the cycle in the linked list. If we apply the Floyd’s alogrithm here, where slow pointer moves as , slow = nums[slow] and fast pointer moves as ,
fast = nums[nums[fast]].
If you make move theses 2 pointers in this fashion then , if a number is duplicated then at least 2 different index will contain that value which essentially form a cycle of imaginary linked list.
See the below link for detailed explanation of Floyd’s Cycle Detection Algorithm
https://dhanarajappu456.medium.com/floyds-cycle-detection-algorithm-dd61bc379bab
class Solution(object):
def findDuplicate(self, nums):
slow=nums[0]
fast =nums[0]
while(True):
slow=nums[slow]
fast=nums[nums[fast]]
if(fast==slow):
break
slow=nums[0]
while(fast!=slow):
slow=nums[slow]
fast=nums[fast]
return slow