• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Ron McLeod
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Liutauras Vilda
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • fred rosenberger
  • salvin francis
Bartenders:
  • Piet Souris
  • Frits Walraven
  • Carey Brown

Best algorithm to find the duplicate number

 
Ranch Hand
Posts: 145
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi All,

This is an interview question faced by my friend and hence posting here looking for some best answers.

There are 100 numbers out of which one number has a duplicate while all other numbers are unique.
What is the best algorithm to find the duplicate number.
Having a for loop/iterating is really a school kids work.
Need some good way out.

I coud think of only quick sort algorithm, as in the process of sorting we can find the duplicate also (checking for the equal value).
Any good suggestions please...!!!

Regards,
Sriram
 
Greenhorn
Posts: 22
MyEclipse IDE Hibernate Postgres Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Sriram,

I think when we talk about efficiency we need to consider Space-time tradeoff.

So I think in this case if time is your criteria and not the space, then sorting the entire array is not a good idea, alternative can be using HashSet. add() and check the returned boolean value, if its false the value that you are adding already exists in the set hence its a duplicate number, Time wise it be more efficient then sorting the entire array but consume more memory space.

Regards
Tarun
 
    Bookmark Topic Watch Topic
  • New Topic