vineetchirania
BAN USER- 0of 0 votes
AnswersFind diameter of a binary tree in O(n)
- vineetchirania in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersGiven 3 prime numbers and an integer k, find the kth number if all the nos which are having these 3 prime numbers as their factors are arranged in increasing order.
- vineetchirania in India
Eg. prime numbers - 2,3,5
The increasing sequence will be 2,3,4,5,6,8,9...| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
Do you know what 'wrong' means? This code is working for every situation. Not searching if already found is a good thing to incorporate but not doing so, in no way, makes the code wrong!
- vineetchirania September 15, 2011You couldn't be more wrong here..kth number or for that matter any number in the series here will only have the 3 prime nos as their factor and no other number could be its factor. If you multiply it by k then k becomes a factor of that number which makes it wrong.
- vineetchirania September 14, 2011<pre lang="" line="1" title="CodeMonkey97684" class="run-this">node *formTree(string& str)
{
int n=str.length();
Stack<node*> mystack;
node *root=NULL;
for(int i=0;i<n;i++){
node *temp=new node;
temp->left=temp->right=NULL;
if(str[i]=='N'){
temp->data='N';
}
else if(str[i]=='L')
temp->data='L';
//cout<<"\nNode constructed. Value is "<<temp->data;
//connect it to the tree
if(!root) root=temp;
else {
while(mystack.isNotEmpty()){
node *tos=mystack.peek();
if(tos->left==NULL){
tos->left=temp;
break;
}
else if(tos->right==NULL){
tos->right=temp;
break;
}
else mystack.pop();
} //end of while
}
if(str[i]=='N') mystack.push(temp);
} //end of for-loop
//if(mystack.isNotEmpty()) cout<<"\nSome error";
return root;
}
</pre><pre title="CodeMonkey97684" input="yes">
</pre>
<pre lang="" line="1" title="CodeMonkey20684" class="run-this">#include"tree.cpp"
struct path{
char where;
path *left;
path *right;
};
struct node{
int data;
node *left;
node *right;
};
int printLargestSumPath(node *root,path **head);
int main()
{
node *root=createTree();
cout<<"\nThe tree has been constructed";
path *head=NULL;
int sum=printLargestSumPath(root,&head);
//Print the path with largest sum
cout<<"\nThe path with largest sum is:\n";
node *temp=root;
while(temp){
cout<<temp->data<<" ";
if(head->where=='L'){
temp=temp->left;
head=head->left;
}
else{
temp=temp->right;
head=head->right;
}
}
cout<<"\nThe largest root to leaf sum is: "<<sum;
cin.ignore(2);
return 0;
}
int printLargestSumPath(node *root,path **head)
{
if(!root) return 0;
path *pl,*pr;
pl=pr=NULL;
int lsum=printLargestSumPath(root->left,&pl);
int rsum=printLargestSumPath(root->right,&pr);
path *temp=new path;
temp->left=pl;
temp->right=pr;
*head=temp;
if(lsum>=rsum){
temp->where='L';
return (lsum+root->data);
}
else{
temp->where='R';
return (rsum+root->data);
}
}
</pre><pre title="CodeMonkey20684" input="yes">
</pre>
If we are allowed to change the structure of linked list (which very often we are not) we can store an extra char variable in the node which just stores 'L' if left is greater otherwise it stores 'R'. When traversing the calculateMaxSum() function we fill this char variable with respective values. After complete traversal we just start from root, printing the elements, go left if the char variable says L otherwise we'll go right. Time Complexity: O(n) Space Complexity: O(n)
If we are not allowed to change the structure then we can create a new tree which just stores whether to go left or right while printing the sum. The program follows. Here also Time Complexity: O(n) Space Complexity: O(n)
But, here we will get those numbers also which have factors one or more of these numbers and some other prime factor as well. For example, one getting 42 your algo will increment count, which it should not since it is having 7 also as a factor.
- vineetchirania September 08, 2011@JuvN : Excellent solution man. Would just like to ask one thing..since it is a heap, which is always balanced, so height of tree will always be log n. Therefore, shouldn,t the worst case complexity be O(nlog n) instead of O(n^2)?
- vineetchirania September 07, 2011<pre lang="" line="1" title="CodeMonkey76273" class="run-this">void findDistance(node *root, int find, int distance, int& maxdistance)
{
if(!root) return;
if(root->data==find) { maxdistance=distance; return; }
findDistance(root->left,find,distance+1,maxdistance);
findDistance(root->right,find,distance+1,maxdistance);
}
int main()
{
node *root=createTree();
int maxdistance=-1;
findDistance(root,25,0,maxdistance);
cout<<"The distance is "<<maxdistance;
cin.ignore(2);
return 0;
}</pre><pre title="CodeMonkey76273" input="yes">
</pre>
and to distinguish between error and success, the output will be -1 if not found.
- vineetchirania September 15, 2011