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.
>> >>> > > > > 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
>>
>> --
>> Regards,
>> Kamakshi
>> kamakshi...@gmail.com- 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.
>
>
--
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.
