Find the number of Enjoyable Chocolates for Geek’s Budget
Geek has gone to a chocolate shop with exactly k coins in his pocket. The shop offers a selection of n chocolates, each with a unique, sorted (in increasing order) price. Geek’s goal is to enjoy the costliest chocolates he can afford. However, he is shy and doesn’t want to ask the shopkeeper about the prices too many times, as he will enquire at most 50 times, the task is to find the number of chocolates Geek will enjoy based on his budget and the chocolate prices in the shop.
Examples:
Input: arr = {2, 4, 6}, K = 5
Output: 1
Explanation: The prices of chocolates are [2, 4, 6] and Geek had 5 coins with him. So he can only buy chocolate that costs 4 coins (since he always picks the costliest one).Input: arr = {1, 2, 3, 4}, k = 9
Output: 3
Explanation: The prices of chocolates are [1, 2, 3, 4] and Geek had 9 coins with him. So he can buy two chocolates that cost 4 coins. Thereafter, he had only 1 coin with him, hence he will have 1 more chocolate (that costs 1 coin).
Approach: To solve the problem follow the below idea:
The idea is to divides the budget by the price of the costliest chocolate to determine how many can be bought. It then performs a binary search to find the most expensive affordable chocolate. This process continues until the budget is exhausted or 50 inquiries are made, giving the maximum number of chocolates Geek can enjoy within the constraints.
Step-by-step approach:
- Create a map to store the prices of chocolates for future reference.
- Create a function called help() that takes a position, a map, and a shop object as parameters.
- Calculate the quotient of k divided by the price of the most expensive chocolate, and add it to the answer.
- Update k to the remainder of k divided by the price of the most expensive chocolate.
- Set l to 0, and initialize r to n.
- Iterate until l is equal to 0.
-
- Perform a binary search to find the largest l value.
- Move l until the price of the chocolate at position l exceeds the remaining budget k.
- If l reaches 0, break the loop.
- Calculate the quotient of k divided by the price of the chocolate at position l, and add it to the answer.
- Update k to the remainder of k divided by the price of the chocolate at position l.
- Return the final answer.
Below is the implementation of the above approach:
C++
#include <iostream> #include <map> #include <vector> using namespace std; // Shop class to simulate the shop where // chocolates are sold class Shop { public : long long get( int position) { // Implement this method to return the // price of the chocolate at the given // position For testing purposes, we'll // provide a simple implementation vector< long long > prices = { 2, 4, 6 }; if (position >= 0 && position < prices.size()) { return prices[position]; } // Return -1 if the position is out // of range else { return -1; } } }; // Macro to define a long long datatype #define ll long long // Solution class to find the maximum number // of chocolates Geek can enjoy class Solution { public : Shop shop; // Constructor to initialize the shop object Solution(Shop s) { this ->shop = s; } // Helper function to get the value // at position q ll help( int q, map< int , ll>& m, Shop& sp) { // If value is already calculated, // return it if (m.find(q) != m.end()) return m[q]; // Calculate and store the value // at position q return m[q] = sp.get(q - 1); } // Main function to find the answer long long find( int n, long long k) { // Create a map to store previously // calculated values map< int , ll> m; // Initialize the answer to 0 long long ans = 0; // Find the quotient and remainder when // k is divided by help(n, m, this->shop) ans += k / help(n, m, this ->shop); k %= help(n, m, this ->shop); // Initialize the left and right indices // for binary search int l = 0, r = n; // Iterate until l is equal to 0 while (1) { // Reset l to 0 l = 0; // Perform binary search to find // the largest value of l while (l + 1 < r) { // Calculate the middle index int mid = (l + r) / 2; // If help(mid, m, this->shop) is // less than or equal to k, update l if (help(mid, m, this ->shop) <= k) l = mid; // Otherwise, update r else r = mid; } // If l is equal to 0, break // the loop if (l == 0) break ; // Update the answer and k ans += k / help(l, m, this ->shop); k %= help(l, m, this ->shop); } // Return the final answer return ans; } }; // Drivers code int main() { // Create a Shop object Shop shop; // Create a Solution object with // the Shop object Solution solution(shop); // Define the number of chocolates // and the budget int n = 3; long long k = 5; // Call the find method to get the maximum // number of chocolates Geek can enjoy long long result = solution.find(n, k); // Output the result cout << "Maximum number of chocolates Geek can enjoy: " << result << endl; return 0; } |
Java
import java.util.HashMap; import java.util.Map; import java.util.Vector; // Shop class to simulate the shop where // chocolates are sold class Shop { public long get( int position) { // Implement this method to return the // price of the chocolate at the given // position For testing purposes, we'll // provide a simple implementation Vector<Long> prices = new Vector<>(); prices.add(2L); prices.add(4L); prices.add(6L); if (position >= 0 && position < prices.size()) { return prices.get(position); } else { // Return -1 if the position is out // of range return - 1 ; } } } // Solution class to find the maximum number // of chocolates Geek can enjoy class Solution { private Shop shop; // Constructor to initialize the shop object public Solution(Shop s) { this .shop = s; } // Helper function to get the value // at position q private long help( int q, Map<Integer, Long> m, Shop sp) { // If value is already calculated, // return it if (m.containsKey(q)) return m.get(q); // Calculate and store the value // at position q long result = sp.get(q - 1 ); m.put(q, result); return result; } // Main function to find the answer public long find( int n, long k) { // Create a map to store previously // calculated values Map<Integer, Long> m = new HashMap<>(); // Initialize the answer to 0 long ans = 0 ; // Find the quotient and remainder when // k is divided by help(n, m, this.shop) ans += k / help(n, m, this .shop); k %= help(n, m, this .shop); // Initialize the left and right indices // for binary search int l = 0 , r = n; // Iterate until l is equal to 0 while ( true ) { // Reset l to 0 l = 0 ; // Perform binary search to find // the largest value of l while (l + 1 < r) { // Calculate the middle index int mid = (l + r) / 2 ; // If help(mid, m, this.shop) is // less than or equal to k, update l if (help(mid, m, this .shop) <= k) l = mid; // Otherwise, update r else r = mid; } // If l is equal to 0, break // the loop if (l == 0 ) break ; // Update the answer and k ans += k / help(l, m, this .shop); k %= help(l, m, this .shop); } // Return the final answer return ans; } } // Driver code public class Main { public static void main(String[] args) { // Create a Shop object Shop shop = new Shop(); // Create a Solution object with // the Shop object Solution solution = new Solution(shop); // Define the number of chocolates // and the budget int n = 3 ; long k = 5 ; // Call the find method to get the maximum // number of chocolates Geek can enjoy long result = solution.find(n, k); // Output the result System.out.println( "Maximum number of chocolates Geek can enjoy: " + result); } } |
Python3
class Shop: def get( self , position): # Implement this method to return the # price of the chocolate at the given # position. For testing purposes, we'll # provide a simple implementation prices = [ 2 , 4 , 6 ] if 0 < = position < len (prices): return prices[position] # Return -1 if the position is out # of range else : return - 1 class Solution: def __init__( self , shop): self .shop = shop # Helper function to get the value # at position q def help ( self , q, m): # If value is already calculated, # return it if q in m: return m[q] # Calculate and store the value # at position q m[q] = self .shop.get(q - 1 ) return m[q] # Main function to find the answer def find( self , n, k): # Create a dictionary to store previously # calculated values m = {} # Initialize the answer to 0 ans = 0 # Find the quotient and remainder when # k is divided by self.help(n, m) ans + = k / / self . help (n, m) k % = self . help (n, m) # Initialize the left and right indices # for binary search l, r = 0 , n # Iterate until l is equal to 0 while True : # Reset l to 0 l = 0 # Perform binary search to find # the largest value of l while l + 1 < r: # Calculate the middle index mid = (l + r) / / 2 # If self.help(mid, m) is # less than or equal to k, update l if self . help (mid, m) < = k: l = mid # Otherwise, update r else : r = mid # If l is equal to 0, break # the loop if l = = 0 : break # Update the answer and k ans + = k / / self . help (l, m) k % = self . help (l, m) # Return the final answer return ans # Drivers code if __name__ = = "__main__" : # Create a Shop object shop = Shop() # Create a Solution object with # the Shop object solution = Solution(shop) # Define the number of chocolates # and the budget n = 3 k = 5 # Call the find method to get the maximum # number of chocolates Geek can enjoy result = solution.find(n, k) # Output the result print (f "Maximum number of chocolates Geek can enjoy: {result}" ) |
C#
using System; using System.Collections.Generic; // Shop class to simulate the shop where // chocolates are sold class Shop { public long Get( int position) { // Implement this method to return the // price of the chocolate at the given // position. For testing purposes, we'll // provide a simple implementation List< long > prices = new List< long > { 2, 4, 6 }; if (position >= 0 && position < prices.Count) { return prices[position]; } else { // Return -1 if the position is out // of range return -1; } } } // Solution class to find the maximum number // of chocolates Geek can enjoy class Solution { private Shop shop; // Constructor to initialize the shop object public Solution(Shop s) { this .shop = s; } // Helper function to get the value // at position q private long Help( int q, Dictionary< int , long > m, Shop sp) { // If value is already calculated, // return it if (m.ContainsKey(q)) return m[q]; // Calculate and store the value // at position q long result = sp.Get(q - 1); m[q] = result; return result; } // Main function to find the answer public long Find( int n, long k) { // Create a dictionary to store previously // calculated values Dictionary< int , long > m = new Dictionary< int , long >(); // Initialize the answer to 0 long ans = 0; // Find the quotient and remainder when // k is divided by Help(n, m, this.shop) ans += k / Help(n, m, this .shop); k %= Help(n, m, this .shop); // Initialize the left and right indices // for binary search int l = 0, r = n; // Iterate until l is equal to 0 while ( true ) { // Reset l to 0 l = 0; // Perform binary search to find // the largest value of l while (l + 1 < r) { // Calculate the middle index int mid = (l + r) / 2; // If Help(mid, m, this.shop) is // less than or equal to k, update l if (Help(mid, m, this .shop) <= k) l = mid; // Otherwise, update r else r = mid; } // If l is equal to 0, break // the loop if (l == 0) break ; // Update the answer and k ans += k / Help(l, m, this .shop); k %= Help(l, m, this .shop); } // Return the final answer return ans; } } // Driver code class MainClass { public static void Main( string [] args) { // Create a Shop object Shop shop = new Shop(); // Create a Solution object with // the Shop object Solution solution = new Solution(shop); // Define the number of chocolates // and the budget int n = 3; long k = 5; // Call the Find method to get the maximum // number of chocolates Geek can enjoy long result = solution.Find(n, k); // Output the result Console.WriteLine( "Maximum number of chocolates Geek can enjoy: " + result); } } |
Javascript
// JavaScript code for the above approach // Shop class to simulate the // shop where chocolates are sold class Shop { get(position) { // Implement this method to return the price // of the chocolate at the given position // For testing purposes, we'll provide a // simple implementation const prices = [2, 4, 6]; if (position >= 0 && position < prices.length) { return prices[position]; } // Return -1 if the position is out of range else { return -1; } } } // Solution class to find the maximum // number of chocolates Geek can enjoy class Solution { constructor(shop) { this .shop = shop; } // Helper function to get the value at position q help(q, m, sp) { // If value is already calculated, return it if (m.has(q)) { return m.get(q); } // Calculate and store the value at position q const value = sp.get(q - 1); m.set(q, value); return value; } // Main function to find the answer find(n, k) { // Create a map to store previously // calculated values const m = new Map(); // Initialize the answer to 0 let ans = 0; // Find the quotient and remainder when k // is divided by help(n, m, this.shop) ans += Math.floor(k / this .help(n, m, this .shop)); k %= this .help(n, m, this .shop); // Initialize the left and right indices // for binary search let l = 0; let r = n; // Iterate until l is equal to 0 while ( true ) { // Reset l to 0 l = 0; // Perform binary search to find the // largest value of l while (l + 1 < r) { // Calculate the middle index const mid = Math.floor((l + r) / 2); // If help(mid, m, this.shop) is less // than or equal to k, update l if ( this .help(mid, m, this .shop) <= k) { l = mid; } else { // Otherwise, update r r = mid; } } // If l is equal to 0, break the loop if (l === 0) { break ; } // Update the answer and k ans += Math.floor(k / this .help(l, m, this .shop)); k %= this .help(l, m, this .shop); } // Return the final answer return ans; } } // Driver code // Create a Shop object const shop = new Shop(); // Create a Solution object with the Shop object const solution = new Solution(shop); // Define the number of chocolates and the budget const n = 3; const k = 5; // Call the find method to get the maximum // number of chocolates Geek can enjoy const result = solution.find(n, k); // Output the result console.log( "Maximum number of chocolates Geek can enjoy: " + result); |
Maximum number of chocolates Geek can enjoy: 1
Time Complexity: O(log n) due to the binary search.
Auxiliary Space: O(1) because the map size is limited by the maximum of 50 entries.