@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.
> > >> >>> > > > > 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- 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.
