@saurav The answer must be 2 because it is the first repeating element . We can find the 1st repeating element by creating a hash map of 1st k+1 elements because we can have at most k distinct elements and after that a digit should repeat.
eg. N=10; k=5; so the array can be 1 2 3 4 5 1..... therefore we can get the 1st repeating element with k+1 elements. T(n)=O(k+1)=O(k) On Thu, Jul 8, 2010 at 1:03 AM, souravsain <souravs...@gmail.com> wrote: > @sharad > > When you say you want first repeating element, do u mean first in the > sense in which numbers are layed out in the array (i mean moving from > left to right in the array, the first element, <=K, that is repeating) > or the first smallest element that is repeating? for example in the > given example > > 2,4,3,6,7,1,2,5,1,2 which has 10 elements, if your answer 2 or 1? > > Sourav > > On Jul 7, 4:52 pm, Satya <satya...@gmail.com> wrote: >> Use selection algorithm, a variation of quicksort algorithm which is in >> place.http://en.wikipedia.org/wiki/Selection_algorithm >> ......... >> Satya >> >> On Wed, Jul 7, 2010 at 1:45 PM, sharad kumar <sharad20073...@gmail.com>wrote: >> >> >> >> > ya i want inplace soln >> >> > -- >> > You received this message because you are subscribed to the Google Groups >> > "Algorithm Geeks" group. >> > To post to this group, send email to algoge...@googlegroups.com. >> > To unsubscribe from this group, send email to >> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> > . >> > For more options, visit this group at >> >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - >> >> - Show quoted text - > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Thanks & Regards Nikhil Agarwal Senior Undergraduate Computer Science & Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
