## 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

Rep**hamishleeh**, Blockchain Developer at ASAPInfosystemsPvtLtdProperty custodian with a reputed organization and help in keeping accurate check over the supplies and inventory of materials and ...

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

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