@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 <[email protected]> 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 <[email protected]> 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 <[email protected]>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 [email protected]. >> > To unsubscribe from this group, send email to >> > [email protected]<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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
