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.
(1) Make class IceCreamIdCostBinding containing int id and int cost.
(2) Capture the List<Integer> cost into a List<IceCreamIdCostBinding> . This costs O(n) to copy one list into another, And then sort this derived list in ascending order based on cost field - worst-case cost: O(n * log(n)), assuming good sort algorithm used by Java underneath.
(3) Do a Binary Search (cost: O(log (n))) through the List to attempt to locate the Ice Cream whose cost == Pooled Money. Let this index be x. If not found, then the entire list will have to be searched. If found, then we can search only the sub-list spanning from index 0 to x - 1.
(4) Iterate through the list from index: 0 to x - 1. And for each element, compute the remainingMoney value. Now, make another Sub-List by omitting the CURRENT element & do another Binary Search in that narrowed sub-list (worst-case cost: O(log (n))) & try to locate the Ice Cream whose cost == remainingMoney. If you find this, then we have found a pair. Print & exit. Else keep looping & continuing.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Hash Tables: Ice Cream Parlor
You are viewing a single comment's thread. Return to all comments →
Explaining the approach taken:
(1) Make
class IceCreamIdCostBindingcontainingint idandint cost.(2) Capture the
List<Integer> costinto aList<IceCreamIdCostBinding>. This costsO(n)to copy one list into another, And then sort this derived list in ascending order based oncostfield - worst-case cost:O(n * log(n)), assuming good sort algorithm used by Java underneath.(3) Do a Binary Search (cost:
O(log (n))) through the List to attempt to locate the Ice Cream whosecost == Pooled Money. Let this index bex. If not found, then the entire list will have to be searched. If found, then we can search only the sub-list spanning from index0tox - 1.(4) Iterate through the list from
index:0tox - 1. And for each element, compute theremainingMoneyvalue. Now, make another Sub-List by omitting the CURRENT element & do another Binary Search in that narrowed sub-list (worst-case cost:O(log (n))) & try to locate the Ice Cream whosecost == remainingMoney. If you find this, then we have found a pair. Print & exit. Else keep looping & continuing.