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