Suppose after first iteration, I iterate through whole array XORring+(1..N)
the last bit and I get 1.
Now, for making sure I don't need process undesirable numbers with last bit
'0', I will need to use sum bool array of size N bits to discard those
numbers or I can do it without using it?
Explanation for others.
Suppose the given array is
- A[6]={ 0,1,2,3,5,6} // Missing number is 4.
- Now, XOR of (1^2^3^^4^5^6)=7(111).==TEMP
- Now, I will get last bit of the all array elements and XOR it with last
bit of TEMP i.e 1, so, 1^A[0][0]^A[1][0]...A[5[0] gives us 0. ( Last bit of
missing number is 0. Correct as 4 was missing).
- Now, I if I will discard all those numbers with last bit 0, I will be
left with (1,3,5)
- Now, 2last last bit of TEMP is 1. And of (1,3,5) is
(0,1,0) receptively. So, I will XOR all these and I will get 0'
- Again after ignoring numbers with 0 as we are only left with 3. Now xor
3rd from last bit with, we get 1.
- So, the Desired number is 100 i.e 4.
Here, as Fetching one bit takes constant time, For the first time we only
fetched O(N) bytes. Next time we fetched O(N/2) and so on we will have to
fetch O(N/4)+O(N/8)..... bites. So, overall time complexity is O(N).
It would have been O(KN) where K is the number of bites in a integer only we
would have fetched all the bites at least once.
~
Oppilas
On Mon, Jun 27, 2011 at 8:38 AM, Dave <dave_and_da...@juno.com> wrote:
> @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.
>
>
--
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.
