Given an array arr[] consisting of the cost of toys and an integer K depicting the amount of money available to purchase toys. The task is to find the maximum number of toys one can buy with the amount K.
Note: One can buy only 1 quantity of a particular toy.
Examples:
Input: arr[] = {1, 12, 5, 111, 200, 1000, 10, 9, 12, 15}, K = 50
Output: 6
Toys with amount 1, 5, 9, 10, 12, and 12
can be purchased resulting in a total amount of 49.
Hence, the maximum number of toys are 6.Input: arr[] = {1, 12, 5, 111, 200, 1000, 10}, K = 50
Output: 4
Approach: Insert all the elements of the given array in a priority_queue now one by one remove elements from this priority queue and add these costs in a variable sum initialised to 0. Keep removing the elements while the new addition keep the sum smaller than K. In the end, the count of elements removed will be the required answer.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count of// maximum toys that can be boughtint maxToys(int arr[], int n, int k){ // Create a priority_queue and push // all the array elements in it priority_queue<int, vector<int>, greater<int> > pq; for (int i = 0; i < n; i++) { pq.push(arr[i]); } // To store the count of maximum // toys that can be bought int count = 0; while (pq.top() <= k) { count++; k = k - pq.top(); pq.pop(); } return count;}// Driver codeint main(){ int arr[] = { 1, 12, 5, 111, 200, 1000, 10 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 50; cout << maxToys(arr, n, k); return 0;} |
Java
// Java implementation of the approach import java.io.*;import java.util.*;class GFG{ // Function to return the count of // maximum toys that can be bought public static int maxToys(int[] arr, int k){ int n = arr.length; // Create a priority_queue and push // all the array elements in it PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); for(int i = 0; i < n; i++) { pq.offer(arr[i]); } // To store the count of maximum // toys that can be bought int count = 0; while (!pq.isEmpty() && pq.peek() <= k) { k = k - pq.poll(); count++; } return count;}// Driver codepublic static void main (String[] args){ int[] arr = new int[]{ 1, 12, 5, 111, 200, 1000, 10 }; int k = 50; System.out.println(maxToys(arr, k)); }}// This code is contributed by ankit bajpai |
Python3
# Python3 implementation of the approach# Function to return the count of# maximum toys that can be bought# importing heapq moduleimport heapqdef maxToys(arr, n, k): # Create a priority_queue and push # all the array elements in it pq = arr heapq.heapify(pq) # To store the count of maximum # toys that can be bought count = 0 while (pq[0] <= k): count += 1 k -= pq[0] # assigning last element of the min heap # to top of the heap pq[0] = pq[-1] # deleting the last element. pq.pop() # pq.pop() is an O(1) operation # maintaining the heap property again heapq.heapify(pq) return count# Driver codearr = [1, 12, 5, 111, 200, 1000, 10]n = len(arr)k = 50print(maxToys(arr, n, k)) |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{ // Function to return the count of // maximum toys that can be bought static int maxToys(int[] arr, int n, int k) { // Create a priority_queue and push // all the array elements in it List<int> pq = new List<int>(); for (int i = 0; i < n; i++) { pq.Add(arr[i]); } pq.Sort(); // To store the count of maximum // toys that can be bought int count = 0; while (pq[0] <= k) { count++; k = k - pq[0]; pq.RemoveAt(0); } return count; } // Driver code static void Main() { int[] arr = { 1, 12, 5, 111, 200, 1000, 10 }; int n = arr.Length; int k = 50; Console.WriteLine(maxToys(arr, n, k)); }}// This code is contributed by divyeshrabadiya07. |
Javascript
<script> // Javascript implementation of the approach // Function to return the count of // maximum toys that can be bought function maxToys(arr, n, k) { // Create a priority_queue and push // all the array elements in it let pq = []; for (let i = 0; i < n; i++) { pq.push(arr[i]); } pq.sort(function(a, b){return a - b}); // To store the count of maximum // toys that can be bought let count = 0; while (pq[0] <= k) { count++; k = k - pq[0]; pq.shift(); } return count; } let arr = [ 1, 12, 5, 111, 200, 1000, 10 ]; let n = arr.length; let k = 50; document.write(maxToys(arr, n, k)); </script> |
4
Time Complexity: O(N*logN)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!