Find the Duplicate Number

Input: nums = [1,3,4,2,2]
Output: 2
Input: nums = [3,1,3,4,2]
Output: 3
Input: nums = [1,1]
Output: 1
Input: nums = [1,1,2]
Output: 1
  • 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

Some approaches that would solve the problem , but against the defined constraints


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])
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 val

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 val
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

--

--

--

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Implementing RabbitMQ and Kafka: common use cases

PubSub with rabbitMQ

Community Spotlight — January 2019 Edition

Creating A Server Authoritative Game System Using Unity’s NEW Transport Layer | Part 3

HttpRepl: A command-line tool for interacting with RESTful HTTP services

5 Useful VSCode Extensions You Don’t Know About

How Amazon AWS Training and Certification Portal deletes Your exams

What Makes A Senior Developer?

#66DaysOfData : Day 1

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Dhanarajappu

Dhanarajappu

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.

More from Medium

KERBEROS Intro and Working:

Resume Building Tips And Tricks

My Internship Experience at IQVIA

Setting a Guinness World Record with Amazon CodeGuru