Ali
BAN USER
Comments (3)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Nice Job. it takes O(n/5)=O(n)
As both 3 and 5 are prime numbers, another approach can be finding prime factors of n. It can be done by O(lgn*sqrt(n)). If n has prime factors greater than 5 then it can not be spiltted.
If not, the number of necessary coins is number of 2s power 2 multiply by number of 3s and 5s. Of course this doesn't give minimum number of coins (e.g. 30 is 10x3 rather than 6x5), which can be modified with another pass.
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
It is not very efficient. Assuming 'A' has m nodes and 'B' has n nodes, it takes O(n), where usually n>>m.
- Ali January 12, 2015Better to find root of A inside the B, O(lg n) then traverse for checking subset by checking subset_left & subset_right. It will take O(m) and the final result will be O(m+lg n)