@Don : Shift all the numbers to the corresponding positions in the first
iteration
And in the second loop check whether the number and the position matches or
not.
O(N) space and O(1) time
constraint : the number's range must be from 0 to N-1
Cheers,
On Wed, Oct 31, 2012 at 3:16 AM, Don <dondod...@gmail.com> wrote:
> In addition, inputs such as {2,2,0} will fail because when you try to
> make zero negative, it doesn't work so well.
> Don
>
> On Oct 30, 5:36 pm, Don <dondod...@gmail.com> wrote:
> > That solution is using the sign bit as extra storage, which is clever,
> > but if you have an array of unsigned integers and N is more than half
> > of the largest unsigned integer, it won't work. There is a way to do
> > it without using the sign bit as extra storage.
> >
> > On Oct 30, 5:16 pm, rahul sharma <rahul23111...@gmail.com> wrote:
> >
> >
> >
> >
> >
> >
> >
> > > i thnik this is the solution...
> http://www.geeksforgeeks.org/archives/9755
> >
> > > On Wed, Oct 31, 2012 at 2:20 AM, Don <dondod...@gmail.com> wrote:
> > > > We can modify the array. The algorithm should work even if we use
> > > > unsigned integers and N is the largest unsigned integer.
> >
> > > > Don
> >
> > > > On Oct 30, 4:42 pm, rahul sharma <rahul23111...@gmail.com> wrote:
> > > > > Can we modify the array???we can make index we visit as negative
> and then
> > > > > if any one already containing -ve..then its repeating
> >
> > > > > On Wed, Oct 31, 2012 at 1:40 AM, Don <dondod...@gmail.com> wrote:
> > > > > > Does your algorithm work if N=4 and the array is {1,1,2,2}.
> >
> > > > > > Don
> >
> > > > > > On Oct 30, 2:32 pm, arumuga abinesh <arumugaabin...@gmail.com>
> wrote:
> > > > > > > if sum of all elements = n(n-1)/2 , no elements are repeated
> > > > > > > else some numbers are repeated
> >
> > > > > > > On Tue, Oct 30, 2012 at 11:57 PM, Don <dondod...@gmail.com>
> wrote:
> > > > > > > > Given an array of N integers in the range 0..N-1, determine
> if any
> > > > > > > > number is repeated in the array.
> > > > > > > > Solution should execute in O(n) time and use constant space.
> > > > > > > > Don
> >
> > > > > > > > --
> > > > > > > > You received this message because you are subscribed to the
> Google
> > > > > > Groups
> > > > > > > > "Algorithm Geeks" group.
> > > > > > > > To post to this group, send email to
> algogeeks@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.
> >
> > > > > > --
> > > > > > You received this message because you are subscribed to the
> Google
> > > > Groups
> > > > > > "Algorithm Geeks" group.
> > > > > > To post to this group, send email to algogeeks@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.
> >
> > > > --
> > > > You received this message because you are subscribed to the Google
> Groups
> > > > "Algorithm Geeks" group.
> > > > To post to this group, send email to algogeeks@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.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.
