Merge two arrays using merging technique. Now use the following:
1. If the number elements is odd then median is (n+1)/2 th element.
2. If the number of elements is even then median is (n/2 th element +
(n/2 +1)-th element )/2.
--
You received this message because you are subscribed to the
Do you mean to convert a BST to a HEAP?
--
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.
as a hint, convert the BST to a sorted array and take two pointers one
pointing to the first number and the other pointing to the last. Then, move
pointers appropriately to find the two numbers summing up to k.
complexity: O(n)
2010/8/5 Seçkin Can Şahin seckincansa...@gmail.com
what about the
the solution elegant..but is there any on the fly method by just exploiting
the BST propertyby using left and right pointers
--
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.
how about using hashing???
at the first collision we will know the repeated element
worst case time here will be ( n/2 +1 )
On Fri, Aug 6, 2010 at 12:04 AM, Anand anandut2...@gmail.com wrote:
http://codepad.org/8eDVyeBT
Using XOR logic we can find Duplicates in O(n)
On Thu, Aug 5,
Two inorders would achieve the same thing without using an array. One
pointer running inorder with LDR and other pointer running inorder with RDL.
Compare the sum at the two nodes and then adjust them accordingly.
On Fri, Aug 6, 2010 at 2:11 PM, Manjunath Manohar
manjunath.n...@gmail.comwrote:
Using median, you can do it!
Thanks,
Sathaiah
On Thu, Aug 5, 2010 at 7:06 PM, AlgoBoy manjunath.n...@gmail.com wrote:
an array in which n/2 elements are unique...and the remaning n/2 have
the same elements but reapeated n/2 times. can anyone suggest a linear
solution with constant space/...
do the inorder traversal of the bst ...this gives the sorted array..
from that use
int i=0,j=length(array)
while(ij)
{
if(array[i]+array[j]sum)
--j;
else if(array[i]+array[j]sum)
++i;
else if((array[i]+array[j])==sum)
return i,j
else
++i,--j;
}
On Fri, Aug 6, 2010 at 3:10 PM, Chonku
.
Is there a quick way to count the number of set bits in this number
manually???
converting that no. in to binary as
int bin(int n)
{
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
@Avik: Correcting/augmenting your post:
N = (3*4096+15*256+3*16+3)
= 3*(2^12) + 15*(2^8) + 3*(2^4) + 3*(2^0)
= (2+1)*(2^12) + (8+4+2+1)*(2^8) + (2+1)*(2^4) + (2+1)
= (2^1+2^0)*(2^12) + (2^3+2^2+2^1+2^0)*(2^8) + (2^1+2^0)*(2^4) +
(2^1+2^0)
= 2^13 + 2^12 + 2^11 + 2^10 + 2^9 + 2^8 + 2^5
no the array is unsorted..
On Thu, Aug 5, 2010 at 9:29 PM, dinesh bansal bansal...@gmail.com wrote:
If I understand the question correctly... there is an array of size n which
has n/2 distinct elements and one element is repeated n/2 times.
For e.g.:
n = 4: 1 2 3 3
n = 61 2 3 4
will this work in two sorted arrays of equal length..
--
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
u need to write a recursive function.
All leaf nodes in complete BST are from n/2+1n.
n/2+1 element will be the beginning element(least left child) for our
resultant sorted array. U can get the parent of the element by doing the
floor(n/2/+1), get the right child of the parent by
typo!
floor(n/2/+1) == floor((n/2/+1)/2)
.
Satya
On Fri, Aug 6, 2010 at 5:27 PM, Satya satya...@gmail.com wrote:
u need to write a recursive function.
All leaf nodes in complete BST are from n/2+1n.
n/2+1 element will be the beginning element(least left child) for our
Chonku, you can do that only when you have the links to parent nodes. I
couldn't come up with a way of doing what you said on a basic BST(nodes
having pointers only to their 2 children) that is why I suggested using an
array. It doesn't change the overall complexity but if you have an idea
about
Hey Anand,
Can you(or anyone who understood it) elaborate on that XOR logic idea of
yours?
Thanks,
Seckin
On Fri, Aug 6, 2010 at 7:14 AM, Manjunath Manohar
manjunath.n...@gmail.comwrote:
no the array is unsorted..
On Thu, Aug 5, 2010 at 9:29 PM, dinesh bansal bansal...@gmail.com wrote:
If
hi anand.. can u write up a pseudocode of ur algorithm using XOR logic
--
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
i kinda understood ...u are doing xor on the array twice..but it dint seem
to work for the array..{2,1,3,2}
please elaborate ur code...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
yeah it does not work. maybe it is only the implementation being wrong, I
want to hear the idea.
On Fri, Aug 6, 2010 at 2:55 PM, Manjunath Manohar
manjunath.n...@gmail.comwrote:
i kinda understood ...u are doing xor on the array twice..but it dint seem
to work for the array..{2,1,3,2}
please
already discussed.
On Fri, Aug 6, 2010 at 11:07 PM, UMESH KUMAR kumar.umesh...@gmail.comwrote:
how to sort specific order the given array ,Without using extra memory
Input:-a1,a2,a3,a4,a5..an,b1,b2,b3,b4,b5..bn.
output:-a1,b1,a2,b2,a3,b3,an.bn
--
You received this
http://cute-actress-images.blogspot.com/
http://actress.0jet.com
http://healthtips.06fr.com
http://actress.0jet.com
http://dailyscience.youblog.net
http://jobs4all.menblogs.net
http://healthtips.06fr.com
http://dailyscience.youblog.net
http://jobs4all.menblogs.net
The thread is waiting for u anand :)..reply soon
--
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
where is it amit... could u pls post the link pls..
--
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
Here's a solution that I am pretty sure is less than O(n^2). The data
are moved only once, but timing the routine suggests that it is O(n
log n), but I have no proof of that.
The first and last do-while loops move cycles of data, while the
nested do-while loops find the beginning index of a new
@algoboy:
If you want to use extra space go with sharad's algo: do inorder traversal
, store in a buffer and use 2 pointer method. T(n) =O(n) , S(n)=O(n)
If you don't want to use extra space , convert BST into circular DLL or DLL
and use 2 pointer algorithm. (conversion of BST into DLL is a
@Algoboy , its pretty difficult to find the duplicate in constant space
unless u mention the range of numbers. Do the numbers lie between [1,n] ???
Unless some other information is given i don't think it is possible to come
out with a proper solution.
--
Thanks Regards,
Priyanka Chatterjee
26 matches
Mail list logo