We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Algorithms
- Search
- Making Candies
- Discussions
Making Candies
Making Candies
Sort by
recency
|
135 Discussions
|
Please Login in order to post a comment
Time Complexity O(log n) Space Complexity O(1)
Intuition & Approach:
We can try all possible round numbers and see if we can make candies in each required number of rounds, however, we notice that if we can produce candies in x rounds then any number of rounds greater than x is redundant to check. SO we can try a round and if we can make the required number of candies we can try for a smaller number of rounds, if we cant then we should try for a higher number of rounds ... this is a binary search! Don’t worry if you didn’t figure that out, recognising this comes with practise.
The check function is a bit complicated since you have to simulate producing candies and trying out purchasing more workers but this can be done if we always check that the current workers and machines setup can reach the required candies before trying to buy an additional worker or machine (which can be done optimally by trying to keep them the same), after which we check again if that setup produces enough for the solution within the rounds and so on. IF we can’t purchase new workers/machines then we have to wait a certain number of rounds (while still producing candies) so we keep checking if we’re reached the target number of candies but if we run out of rounds at any point we return False.
By carefully implementing the check function, this question becomes fairly straightforward! spend time understanding the check function for yourself and what each section is doing to solidify your understanding.
Implementation
100% Javascript solution that should be easy to understand
Can I make greater than or equal to required candies or it should be exactly n ??