@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 <[email protected]> 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 <[email protected]> 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 > > <[email protected]>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 > >> <[email protected]>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 . > >>> <[email protected]>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 <[email protected]>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 [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. > > >>> -- > >>> 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 [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. > > > -- > > 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 [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. > > -- > 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 [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.
