anurag.gupta108
BAN USER- 1of 1 vote
AnswersGiven an N x M matrix having only positive values, we have to nullify the matrix i.e make all entries 0.
- anurag.gupta108 in United States
We are given two operations
1) multiply each element of any one column at a time by 2.
2) Subtract 1 from all elements of any one row at a time
Find the minimum number of operations required to nullify the matrix.
Note: no range of input was given| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
try to read question properly and test your answer before answering
- anurag.gupta108 December 20, 2012I am sorry for the mistake in problem statement.
I have corrected it now
Thank you
This can be solved in O(n) time and O(n) space
maintain cumulative sum in each node this requires O(n) space.
and each left and right subtree will return to its parent the maximum path from their parent to any leaf downwards.The value of F(X, Y) would then be the sum of value returned by left and right subtree minus the cumulative sum of the parent node.
In the end maxSum will store the max F(X, Y)
to print the solution we would need to traverse the tree again, but thats easy
here is the code::
int solve (node * root, int prevSum, int *maxSum) {
if (root == null) { return 0; }
root->cumulativeSum = root->data + prevSum;
if (root->left == null && root->right == null) { // if node is a leaf node
return root->cumulativeSum;
}
leftValue = solve(root->left, root->cumulativeSum, &maxSum);
rightValue = solve(root->right, root->cumulativeSum, &maxSum);
// update the cumulativeSum which will now store the largest F(X, Y) of the leaf nodes having
// current node as LCA.
root->cumulativeSum = leftValue + rightValue - 3 * root->cumulativeSum;
if (root->cumulativeSum > *maxSum) {
*maxSum = root->cumulativeSum;
}
// return the max of the parent to leaf path from the current node
return max(leftValue, rightValue);
}
This can be done in linear time and constant extra space
There are three steps:
Suppose number of nodes in first BST is n and in Second BST is m.
Step 1:: Convert both the BSTs to DLL this takes O(n) + O(m) time and O(1) space
Step 2:: merge the two DLLs in place this takes O(n+m) time and O(1) space
Step 3:: Convert the merged DLL to BST this takes O(n+m) time and O(1) space
Step 1 and 2 are very easy.
Step 3 is the trickiest one , refer to this post :: geeksforgeeks.org/archives/18611
What about the node above the given node in the tree??
- anurag.gupta108 December 20, 2012