@Dave @Mukesh
yaa got it... so simple... i was needlessly making it complex....
thankyou guys .....
On Tue, Oct 5, 2010 at 2:09 AM, Dave <dave_and_da...@juno.com> wrote:
> @Coolfrog$: It sounds like you think there are n items in each list,
> but the problem statement says that the total number of items in the
> lists is n. In your example, n = 12.
>
> Dave
>
> On Oct 4, 2:16 pm, "coolfrog$" <dixit.coolfrog.div...@gmail.com>
> wrote:
> > @Dave
> > yes it help very much...i thank you for these...
> > but still one doubt
> >
> > 1.from first element of each sequence we have made a heap
> > 2. now only n-1 element remains in all k seqences. ====> total (=
> k*(n-1))
> > elememts
> > 3.*"loop is executed once for each output element = once for each
> > element in the input sequences" but there are k sequence...
> > so the loop must run for *k*(n-1) and each iteration of for loop
> running
> > cost to O(log k).
> > overall complexity can be
> > O(k(n-1)log k)..
> >
> > plz do correct me Dave....
> > thanks..
> >
> >
> >
> >
> >
> > On Mon, Oct 4, 2010 at 11:20 PM, Dave <dave_and_da...@juno.com> wrote:
> > > @Coolfrog$: There must have been a communication gap.
> > > The initial heap consists of the first element of each sequence: 2,
> > > 17, 6.
> > > Looping, we output 2, then replace it in the heap with 3 and restore
> > > the heap condition: 3, 17, 6.
> > > Output 3, replace it with 4: 4, 17, 6.
> > > Output 4, replace it with 5: 5, 17, 6.
> > > Output 5. There is nothing left in sequence 1, so the heap now has 2
> > > elements: 17, 6. Restore the heap condition: 6, 17. Output 6, replace
> > > it with 9: 9, 17.
> > > Etc. Etc.
> > > Finally, after outputting 15, list 3 is exhausted, and the heap
> > > consists of 1 element. At this point, the effect of the loop is that
> > > list 2 is output.
> >
> > > The loop is executed once for each output element = once for each
> > > element in the input sequences; i.e., n times.
> >
> > > Does that help?
> >
> > > Dave
> >
> > > On Oct 4, 12:09 pm, "coolfrog$" <dixit.coolfrog.div...@gmail.com>
> > > wrote:
> > > > @Dave
> > > > 1. if three sequence given are 2,3,4,5
> > > > 17,20,31,50
> > > > 6,9,10,15
> > > > while running we will get 2,3,4,5 as sequence no.1 vanishes form
> where to
> > > > choose next element. for heap . (algo.??)
> > > > 2.
> > > > Loop until the heap is empty:
> > > > output the top of the heap,
> > > > replace it with the next element from the list it came from (if
> > > > non-empty, of course),
> > > > re-establishing the heap condition.*========> O(log k).
> >
> > > > "**loop is executed n times**" .. i am not getting because we have
> > > already
> > > > executed loop n-1 times in arranging 3,4,5. **what about rest of
> > > elements...
> >
> > > > Correct me plz
> >
> > > > Regards...**
> > > > *
> >
> > > > On Mon, Oct 4, 2010 at 7:35 PM, Dave <dave_and_da...@juno.com>
> wrote:
> > > > > @saurabh:
> >
> > > > > For the base conversion problem, simulate long division in base B1
> of
> > > > > dividing the number by B2. The remainder is the rightmost digit of
> the
> > > > > conversion. To get the next digit, divide the quotient from the
> first
> > > > > long division by B2 to get the remainder. Repeat for successive
> digits
> > > > > until the quotient is zero.
> >
> > > > > For the merge problem, assuming ascending order:
> >
> > > > > form a min-heap from the first items from each list.
> > > > > Loop until the heap is empty:
> > > > > output the top of the heap,
> > > > > replace it with the next element from the list it came from (if
> > > > > non-empty, of course),
> > > > > re-establishing the heap condition.
> >
> > > > > The loop is executed n times, and each involves O(k) operations.
> >
> > > > > Dave
> >
> > > > > On Oct 4, 7:16 am, saurabh agrawal <saurabh...@gmail.com> wrote:
> > > > > > hi mukesh...gr8 solution....can u pls help me with some other
> > > questions:
> > > > > > --Given an array of n integers find all the inversion pairs in
> O(n)
> > > > > > Inversion pair is one where a[i]>a[j], i<j
> >
> > > > > > --Convert a number given in base B1 to a number in base B2
> without
> > > using
> > > > > any
> > > > > > intermediate base
> >
> > > > > > --You are given k sorted lists with total n inputs in all the
> lists
> > > > > devise a
> > > > > > algorithm to merge them into one single sorted list in O(n logk)
> >
> > > > > > On Mon, Oct 4, 2010 at 5:31 PM, Mukesh Gupta <
> > > mukeshgupta.2...@gmail.com
> > > > > >wrote:
> >
> > > > > > > The problem could be solved using xor logic. First take xor of
> all
> > > the
> > > > > > > elements .Doing that we get a value which is xor of the two non
> > > > > repeating
> > > > > > > elements(as xor of similar values is 0). Now xor of two non
> > > repeating
> > > > > > > numbers contains bits set at those places where the two numbers
> > > differ.
> > > > > Now
> > > > > > > if we take any set bit of our result and again xor all those
> values
> > > of
> > > > > set
> > > > > > > where that bit is set we get first non-repeating value. Taking
> xor
> > > of
> > > > > all
> > > > > > > those values where that bit is not set gives the another
> > > non-repeating
> > > > > > > number..
> > > > > > > For ex
> > > > > > > let a[]={2,3,4,3,2,6}
> >
> > > > > > > xor of all values=0010
> > > > > > > Now we need to get any set bit. We can extract the rightmost
> set
> > > bit of
> > > > > any
> > > > > > > number n by taking ( n & ~(n-1))
> >
> > > > > > > Here 2nd bit is the rightmost set bit.
> >
> > > > > > > Now when we take xor of all values where 2nd bit is set(this
> could
> > > be
> > > > > done
> > > > > > > as (a[i] & 0010) , we get 6
> > > > > > > Taking xor of all values where 2nd bit is not set yields 4.
> >
> > > > > > > Mukesh Gupta
> > > > > > > Delhi College of Engineering
> >
> > > > > > > On Mon, Oct 4, 2010 at 3:17 PM, malli <mallesh...@gmail.com>
> > > wrote:
> >
> > > > > > >> I have an array. All numbers in the array repeat twice except
> two
> > > > > > >> numbers which repeat only once. All the numbers are placed
> > > randomly.
> > > > > > >> Goal is to find out efficiently the two numbers that have not
> > > > > > >> repeated with O(1) extra memory. Expecting linear solution.
> >
> > > > > > >> --
> > > > > > >> You received this message because you are subscribed to the
> Google
> > > > > Groups
> > > > > > >> "Algorithm Geeks" group.
> > > > > > >> To post to this group, send email to
> algoge...@googlegroups.com.
> > > > > > >> To unsubscribe from this group, send email to
> > > > > > >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com>
> > > <algogeeks%2bunsubscr...@googlegroups.com>
> > > > > <algogeeks%2bunsubscr...@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
> algoge...@googlegroups.com.
> > > > > > > To unsubscribe from this group, send email to
> > > > > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com>
> > > <algogeeks%2bunsubscr...@googlegroups.com>
> > > > > <algogeeks%2bunsubscr...@googlegroups.com>
> > > > > > > .
> > > > > > > For more options, visit this group at
> > > > > > >http://groups.google.com/group/algogeeks?hl=en.-Hidequoted 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 algoge...@googlegroups.com.
> > > > > To unsubscribe from this group, send email to
> > > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com>
> > > <algogeeks%2bunsubscr...@googlegroups.com>
> > > > > .
> > > > > For more options, visit this group at
> > > > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > > > --
> > > > *Divesh*
> > > > (¨`·.·´¨) Always
> > > > `·.¸(¨`·.·´¨ ) Keep
> > > > (¨`·.·´¨)¸.·´Smiling!
> > > > `·.¸.·´" Life can give u 100's of reason 2cry,but u can give life
> > > 1000's
> > > > of reasons 2Smile"- 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 algoge...@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com>
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > *Divesh*
> > (¨`·.·´¨) Always
> > `·.¸(¨`·.·´¨ ) Keep
> > (¨`·.·´¨)¸.·´Smiling!
> > `·.¸.·´" Life can give u 100's of reason 2cry,but u can give life
> 1000's
> > of reasons 2Smile"- 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 algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
*Divesh*
(¨`·.·´¨) Always
`·.¸(¨`·.·´¨ ) Keep
(¨`·.·´¨)¸.·´Smiling!
`·.¸.·´" Life can give u 100's of reason 2cry,but u can give life 1000's
of reasons 2Smile"
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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.
