So, if the space doesnt matter. We can have an array A for hashing. So first we will find the minimum element in array suppose M. and in the other traversal of array, we will calculate for each element Ai in array Ai + (-M). So if it exceeds N then elements are not consecutive and other check that you will have to make is that it is already present in Array A. It goes in O(n).
On Jun 26, 5:22 am, "oppilas ." <[email protected]> wrote: > Divye Thanks for the link. > Quoting the top answer from there. > > "Under the assumption numbers less than one are not allowed and there > are no duplicates, there is a simple summation identity for this - the > sum of numbers from 1 to m in increments of 1 is (m * (m + 1)) / 2. > You can then sum the array and use this identity. > > You can find out if there is a dupe under the above guarantees, plus > the guarantee no number is above m or less than n (which can be > checked in O(N)) > > The idea in pseudo-code: > 0) Start at N = 0 > 1) Take the N-th element in the list. > 2) If it is not in the right place if the list had been sorted, check > where it should be. > 3) If the place where it should be already has the same number, you > have a dupe - RETURN TRUE > 4) Otherwise, swap the numbers (to put the first number in the right place). > 5) With the number you just swapped with, is it in the right place? > 6) If no, go back to step two. > 7) Otherwise, start at step one with N = N + 1. If this would be past > the end of the list, you have no dupes. > > And, yes, that runs in O(N) although it may look like O(N ^ 2) > " > > On 6/26/11, DK <[email protected]> wrote: > > > > > > > > > @Chinna: Your algorithm is simple quicksort with partition selection using > > medians. O(n log n) worst case. > > @Varun: You cannot prove that your algorithm will work for all cases. Hence, > > claiming a worst case bound of O(n) is incorrect. > > >http://stackoverflow.mobi/question177118_Algorithm-to-determine-if-ar... > > > -- > > DK > > >http://twitter.com/divyekapoor > >http://www.divye.in > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To view this discussion on the web visit > >https://groups.google.com/d/msg/algogeeks/-/rRP-R-G2MM4J. > > 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. -- 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.
