@Sunny. You are reading too much into that. There is no mention that
the data are 32-bit integers. Perhaps they are big integers. What we
know is that the data are not characters, real numbers, rational
numbers, floating point, etc.
Your algorithm is O(n*w), where w is the word size. As I said, a
divide-and-conquer algorithm can find the missing number in O(n).
Furthermore, this is independent of the word size.
Dave
On Jun 24, 11:44 pm, sunny agrawal <sunny816.i...@gmail.com> wrote:
> @Dave it is given in Question that elements of array are integer
>
>
>
>
>
> On Sat, Jun 25, 2011 at 7:17 AM, Dave <dave_and_da...@juno.com> wrote:
> > @Sunny: What makes you think that the integers are 32 bits in length.
> > Remember that O(.) notation applies as n --> infinity. Thus, O(n log
> > n) is correct for a naive algorithm. But a little thought can give a
> > divide-and-conquer algorithm which is O(n).
>
> > Dave
>
> > On Jun 24, 8:44 am, sunny agrawal <sunny816.i...@gmail.com> wrote:
> > > hmm i also doubt that
> > > but it is Strictly O(32n) not O(nlgn) where lgn <= 32 depending upon
> > value
> > > of n
>
> > > On Fri, Jun 24, 2011 at 1:10 PM, rizwan hudda <rizwanhu...@gmail.com>
> > wrote:
> > > > @sunny: Think again, your solution will take O(n*log(n)), where log(n)
> > is
> > > > the number of bits to represent
> > > > the number.
>
> > > > On Thu, Jun 23, 2011 at 6:51 PM, Sriganesh Krishnan <2448...@gmail.com
> > >wrote:
>
> > > >> can you explain me....what the logic is...behind the xor
> > operation?...is
> > > >> it like inversion or encryption?
>
> > > >> On Thu, Jun 23, 2011 at 11:59 AM, sunny agrawal <
> > sunny816.i...@gmail.com>wrote:
>
> > > >>> initially compute xor of all the values from 0 to n in a variable
> > Temp
> > > >>> so temp = 0^1^2........^n
> > > >>> let result is used to store the missing number
> > > >>> for each ith bit of missing number where i = 0-31 we can find it as
> > > >>> following
> > > >>> ith bit of result = (xor of all ith bits of values of array) xored
> > with
> > > >>> (ith
> > > >>> bit of temp)
>
> > > >>> On Thu, Jun 23, 2011 at 12:25 AM, oppilas . <
> > jatka.oppimi...@gmail.com>wrote:
>
> > > >>>> Is the array sorted?
> > > >>>> In A[1..n], one number is missing from 0 to N. So,
> > > >>>> A[5]={--INF, 2,1,3,0} is a valid case?
>
> > > >>>> On Wed, Jun 22, 2011 at 11:51 PM, RollBack <rajeevr...@gmail.com
> > >wrote:
>
> > > >>>>> An array A[1...n] contains all the integers from 0 to n except for
> > one
> > > >>>>> number which is
> > > >>>>> missing. In this problem, we cannot access an entire integer in A
> > with
> > > >>>>> a single opera-
> > > >>>>> tion. The elements of A are represented in binary, and the only
> > > >>>>> operation we can use
> > > >>>>> to access them is “fetch the jth bit of A[i]”, which takes constant
> > > >>>>> time. Write code to
> > > >>>>> find the missing integer. Can you do it in O(n) time?
> > > >>>>> _
> > > >>>>> _ _____________________________________________
>
> > > >>>>> Rajeev N Bharshetty
> > > >>>>> I Blog @www.opensourcemania.co.cc
>
> > > >>>>> --
> > > >>>>> 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.
>
> > > >>> --
> > > >>> Sunny Aggrawal
> > > >>> B-Tech IV year,CSI
> > > >>> Indian Institute Of Technology,Roorkee
>
> > > >>> --
> > > >>> 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.
>
> > > > --
> > > > Thanks and regards
> > > > Rizwan A Hudda
> > > >http://sites.google.com/site/rizwanhudda
>
> > > > --
> > > > 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.
>
> > > --
> > > Sunny Aggrawal
> > > B-Tech IV year,CSI
> > > Indian Institute Of Technology,Roorkee- 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 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.
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee- 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 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.
