@Sanket: Yes. That is the first O(n) in my previous posting http://groups.google.com/group/algogeeks/msg/cd32a2276c6a2d22.
Dave On Jun 26, 6:55 pm, Sanket <vasa.san...@gmail.com> wrote: > Thanks Dave. > > Won't "Also, calculate the xor of the low order bits of the data" > require you to access each value in the array once? Or am I not > understanding what you meant? > > On Jun 26, 6:50 pm, Dave <dave_and_da...@juno.com> wrote: > > > > > @Sanket: Sure. 0^1^2^...^N is periodic with period 4. Thus, only the > > last two bits of N need be considered, i.e., N & 3. You could index > > into an array A[] = {0,1,1,0}, or note that 0110 in binary is 6, so > > the expression can be evaluated with bit operations by (6 >> (N & 3)) > > & 1. Also, calculate the xor of the low order bits of the data. If the > > two quantities agree, you know that the low order bit of the missing > > data is 0, else it is 1. > > > Dave > > > On Jun 26, 5:23 pm, Sanket <vasa.san...@gmail.com> wrote: > > > > Dave - Can you elaborate on how you can do this - "you can determine > > > whether the low order bit of the missing number is 0 or 1" > > > > On Jun 26, 2:32 pm, Kamakshii Aggarwal <kamakshi...@gmail.com> wrote: > > > > > thanks dave.. > > > > > On 6/26/11, Dave <dave_and_da...@juno.com> wrote: > > > > > > @Kamakshii: In O(n), you can determine whether the low order bit of > > > > > the missing number is 0 or 1. You can eliminate the approximately n/2 > > > > > numbers that do not have this low order bit. Then, in O(n/2), you can > > > > > determine the next-to-low order bit. Etc. O(n) + O(n/2) + O(n/4) + ... > > > > > = O(n). > > > > > > Dave > > > > > > On Jun 26, 2:41 am, Kamakshii Aggarwal <kamakshi...@gmail.com> wrote: > > > > >> @dave:can u please give the divide and conquer solution > > > > > >> On 6/26/11, Kamakshii Aggarwal <kamakshi...@gmail.com> wrote: > > > > > >> > @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.- Hide quoted text - > > - Show quoted text -... > > read more » -- 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.