crackyCoder
BAN USERI have a doubt on this .......
j is represented to state whether the individual DP has j types of packs
so in the Table that we are constructing , when we say
A[i][j] = true if A[i-packs[k]][j] is true
shouldn't k be iterated over all the pack sizes to check ?
I mean for the same problem above if let's say n = 80
and packs[]={6,9,20}
then A[80][1] should be true , because we can solve this problem by taking packs of 20's
but when i try to check for A[80 - pack[0]][1] , or A[80-pack[1]][1] it will fail
beacuse i did not require pack's of six or nine
So essentially what I'm saying is that , in the for loop of k , the limit should be pack.size() and not j ;;
Correct me if I'm wrong !!!!!!
and if I'm right , happy to help :)
Write a recursive function to calculate the height , if height(node) = k , push them into a stack
finally pop out everything from the stack
( Note take height of leaf node =0)
------------- Time Complexity : O(n)
------------ Space Complexity : O(1)
Optimed solution for time :-
memoize the recursion
i.e - store the heights of every node you calculate in a hash table
and then check first if the hash map has a value of height for this node in recursion
if present return the value from hash map , else do the recursion
Time Complexity ------------- O(n)
Space Complexity ----------- O(n)
well ...........
excellent thought though.... can put the interviewer in a tough spot :)
There is one way to do this ( but there's a catch , only problem is , we cannot maintain the structure of the tree)
Step 1. - > Convert the Binary tree to a doubly linked list O(n) time
# Search in google for this solution
Step 2 . -> Now you can to your array thing here, but with pointers , one from left
and one from right
and then we should multiply all 2's to make 4's and all 3's to make 9
if we have even of both(2's and 3's)---> do nothing
both odd----> multiply the remaining 2 and 3
and then sort to give the minimum number
Rephamishleeh, Blockchain Developer at ASAPInfosystemsPvtLtd
Property custodian with a reputed organization and help in keeping accurate check over the supplies and inventory of materials and ...
The problem is much more simpler than some of the solutions.
Since we only have english alphabets whose encoded space is between 1 and 26.
The only time there is an ambiguity in decoding is when the character is 1 or 2.
The other special case is 0.
Here is a sample code.// No validations done
- crackyCoder June 18, 2016