@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>
> > >> .
> > >> 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>
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.- 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.
