@aditya:it is given in the question that u cannot access the entire element in single operaion..therefore both your above solution do not hold for this question.
On 6/25/11, sunny agrawal <sunny816.i...@gmail.com> wrote: > @Dave > yes u r right that integers means it can be big integers too. > generally when we talk about integers, they are 32 bit integers in > Programing/Algorithm Questions > so i was assuming that here > > and about my solution - yes it will be O(nlgn) or O(nw) not acceptable for > given Q :( > > and yes a Divide and Conquer solution can do it in O(n). I just came to know > ..thanks > i little bit similer to my approach............Nice One > > On Sat, Jun 25, 2011 at 9:15 PM, Dave <dave_and_da...@juno.com> wrote: > >> @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. >> >> > > > -- > 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. > > -- Regards, Kamakshi kamakshi...@gmail.com -- 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.