Re: [algogeeks] LCA of a Binary tree not a binary search tree
Node *LCA(node *root, node *e1, node *e2, int x)
{
Node *temp =NULL;
Int y = 0;
If (root-left) temp = LCA(root-left, e1, e2, y);
x+=y;
if (temp) return temp;
if (x==2) return node;
y = 0;
If (root-right) temp = LCA(root-right, e1, e2, y);
x+=y;
if (temp) return temp;
if (x==2) return node;
If (root == e1 || root == e2) x++;
Return null;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
[algogeeks] Re: kth smallest element
This is a beautiful way to express the algorithm. The magic that Don has omitted is that just as in normal binary search, you can hypthesize that A[i] is the k'th element meaning that A[1..i-1] = k, which forces you to conclude the other k-i elements must be in the prefix of B, which is B[1..k-i]. This can be true only if B[k-i] = A[i] = B[k-i+1]. That is, A[i]'s value fits in the gap just after the prefix. If on the other hand A[i] is excessively small, B[1..k-i] A[i], there are not enough small B elements to make k that are at most A[i], and we must consider larger i. On the other hand if A[i] is too big, A[i] B[k-i+1], then there are too many small B elements to make exactly k. So we much consider smaller i values. Of course the search in array A can fail completely because the k'th element might be in B. When it fails, we can just reverse the roles of A and B and search again. There are indexing details to work out for cases where k = i, |A|,|B| k, etc. And you must be careful about duplicate values. But these are just icing. On Nov 15, 10:54 am, Don dondod...@gmail.com wrote: Use a binary search to find a value i in the range 1..k such that A[i] = B[k-i] and A[i] = B[k-i+1], in which case A[i] is the result or A[i] = B[k-i] and A[i+1] B[k-i], in which case B[k-i] is the result Don On Nov 10, 10:07 am, shady sinv...@gmail.com wrote: Given two sorted arrays, how to find the kth smallest element in the union of the arrays in a logarithmic time algorithm ? i have already formed a recursive solution, can anyone give the iterative approach, only pseudo-code :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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.
[algogeeks] Google Question--Suggest Algo
Given a string of lowercase characters, reorder them such that the same
characters are at least distance d from each other.
Input: { a, b, b }, distance = 2
Output: { b, a, b }
How to approach this question ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
Re: [algogeeks] Re: spoj problem
hi don i have now implemented it with bfs but it's still giving wrong
answer can you please tell the test case
#includestdio.h
int a[1000100][2];
int visited[1000100],i,q[1000100];
int main()
{
int f,s,g,u,d;
scanf(%d%d%d%d%d,f,s,g,u,d);
for( i = 1 ; i = f;i++)
{
if(i + u f)
{
a[i][0] = i;
}
else
{
a[i][0] = i + u;
}
if( i - d 1)
{
a[i][1] = i;
}
else
{
a[i][1] = i - d;
}
visited[i] = 0;
}
/*for( i = 1 ;i = f; i++)
{
printf(%d %d %d\n,i,a[i][0],a[i][1]);
}*/
int front ,rear;
front = 0;
rear = 0;
q[0] = s;
visited[s] = 1;
front = 0;
int count = 0,flag = 0;
int p = 0;
while(front = rear)
{
int h ;
/*for( h = front ;h= rear ;h++)
{
printf(%d ,q[h]);
}*/
if(!visited[a[q[front]][0]])
{
if(a[q[front]][0] == g)
{
flag = 1;
count++;
break;
}
p = 1;
q[++rear] = a[q[front]][0];
visited[a[q[front]][0]] = 1;
}
if(!visited[a[q[front]][1]])
{
if(a[q[front]][1] == g)
{
flag = 1;
count++;
break;
}
p = 1;
q[++rear] = a[q[front]][1];
visited[a[q[front]][1]] = 1;
}
if( p == 1)
count++;
p = 0;
front++;
/*printf(\n);
scanf(%d,h);*/
}
if(flag == 0)
{
printf(use the stairs\n);
}
else
{
printf(%d\n,count);
}
return 0;
}
On Wed, Nov 16, 2011 at 4:06 AM, Don dondod...@gmail.com wrote:
This input
100 1 5 5 91
Should output 20. Yours says Take the stairs.
100 1 5 5 89
Should output 76. Yours says Take the stairs.
Don
On Nov 14, 8:27 am, Anshul AGARWAL anshul.agarwa...@gmail.com wrote:
problem ishttp://www.spoj.pl/problems/ELEVTRBL/
and my solution is give wrong answer on spoj . Plz help me to find in
which
case my solution give wrong answer.
*
#includeiostream
**
#includestdio.h
using namespace std;
int main()
{
long long int f,s,u,d,g,c,p;
scanf(%lld%lld%lld%lld%lld,f,s,g,u,d);
p=0;
if(s==g)
printf(0\n);
if(sgu==0d!=0)
{
int temp=s-g;
if((temp/d)*d==temp)
{
p=temp/d;
printf(%lld\n,p);
}
else
printf(use the stairs\n);
}
else if(sg)
{
int temp =s;
s=g;
g=temp;
// cout2endl;
}
//cout1endl;
c=s;
if(sg)
{ while(1)
{
int temp=g-c;
int q;
if(u==0)
{
if(c==g)
{
printf(0\n);
break;
}
else
{
printf(use the stairs\n);
break;
}
}
if(temp/u==(temp/u)*u)
{
q=temp/u;
}
else
q=temp/u+1;
if((c+q*u)=f)
{ // cout1endl;
p=p+q;
c=(q)*u+c;
//coutcendl;
}
else
{//cout2endl;
p=p+temp/u;
c=(temp/u)*u+c;
}
if(c==g)
{
// cout3endl;
printf(%lld,p);
break;
}
if(u==d||d==0||((u%d==0)d!=0)||(d%u==0u!=0))
{
printf(use the stairs\n);
break;}
if(c-d=0)
{ // cout4endl;
c=c-d;
p+=1;
// coutcendl;
}
else
{
// cout5endl;
printf(use the stairs\n);
break;
}
}
}
}
Anshul Agarwal
Nit Allahabad
Computer Science**
*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Re: [algogeeks] Re: spoj problem
thanx Don.
i think my logic is not so good . now i try to make it using bfs .
*Anshul Agarwal
Nit Allahabad
Computer Science**
*
On Tue, Nov 15, 2011 at 5:36 PM, Don dondod...@gmail.com wrote:
This input
100 1 5 5 91
Should output 20. Yours says Take the stairs.
100 1 5 5 89
Should output 76. Yours says Take the stairs.
Don
On Nov 14, 8:27 am, Anshul AGARWAL anshul.agarwa...@gmail.com wrote:
problem ishttp://www.spoj.pl/problems/ELEVTRBL/
and my solution is give wrong answer on spoj . Plz help me to find in
which
case my solution give wrong answer.
*
#includeiostream
**
#includestdio.h
using namespace std;
int main()
{
long long int f,s,u,d,g,c,p;
scanf(%lld%lld%lld%lld%lld,f,s,g,u,d);
p=0;
if(s==g)
printf(0\n);
if(sgu==0d!=0)
{
int temp=s-g;
if((temp/d)*d==temp)
{
p=temp/d;
printf(%lld\n,p);
}
else
printf(use the stairs\n);
}
else if(sg)
{
int temp =s;
s=g;
g=temp;
// cout2endl;
}
//cout1endl;
c=s;
if(sg)
{ while(1)
{
int temp=g-c;
int q;
if(u==0)
{
if(c==g)
{
printf(0\n);
break;
}
else
{
printf(use the stairs\n);
break;
}
}
if(temp/u==(temp/u)*u)
{
q=temp/u;
}
else
q=temp/u+1;
if((c+q*u)=f)
{ // cout1endl;
p=p+q;
c=(q)*u+c;
//coutcendl;
}
else
{//cout2endl;
p=p+temp/u;
c=(temp/u)*u+c;
}
if(c==g)
{
// cout3endl;
printf(%lld,p);
break;
}
if(u==d||d==0||((u%d==0)d!=0)||(d%u==0u!=0))
{
printf(use the stairs\n);
break;}
if(c-d=0)
{ // cout4endl;
c=c-d;
p+=1;
// coutcendl;
}
else
{
// cout5endl;
printf(use the stairs\n);
break;
}
}
}
}
Anshul Agarwal
Nit Allahabad
Computer Science**
*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
[algogeeks] Google Question--Suggest Algo
Start with counting sort of the input. Use shuffling algorithm on it. Store index as cumulative sums of counts. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/0Uoq_OqBLn8J. To post to this group, send email to algogeeks@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.
