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