{"id":1284,"date":"2020-06-10T19:01:00","date_gmt":"2020-06-10T19:01:00","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1284"},"modified":"2022-03-23T11:07:22","modified_gmt":"2022-03-23T11:07:22","slug":"aman-and-shopping","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/aman-and-shopping\/","title":{"rendered":"Aman and Shopping"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Sorting<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

For a given array A<\/code>, find the total number of elements you can pick in given capacity X<\/code>. You can’t pick any item twice.<\/p>\n<\/blockquote>\n

Test case<\/h4>\n
Input:\n1\n5 10\n7 6 3 4 2\n\nOutput:\n3\n\nExplanation:\nWe can pick 2,4, and 3 together. Total sum is 9 which is less than credit available i.e. 10. Hence we cannot pick any more items, we print 3 as answer.<\/code><\/pre>\n
<\/strong><\/u><\/a><\/p>\n
Solving Approach :<\/h3>\n
Bruteforce Approach<\/strong>:<\/p>\n
\n
1) We can pick item by item and check if its already been picked or not, if no we add its value to sum. Along with this, we also check that by adding this element, value of sum must not go more than allowed credit.
\n2) Using this approach we take different number of permutations such that sum of item values must be less than allowed capacity and total numbers of items picked is maximum.
\n3) To check all permuations, it takes O(N!) time, where N is size of array. This approach is highly inefficient for current constraints, so we move to a more efficient approach.<\/p>\n<\/blockquote>\n
Efficient Approach<\/strong>:<\/p>\n
\n
1) If we pick item with least value, and then picking item with second least value, and so on. We can pick maximum items with least sum possible. So, we follow this approach.
\n2) As we have to pick only unique values, so we truncate all duplicate elements. After truncating, we’re left with unique elements only. For example, let’s assume provided array is [1,2,3,3,4,4,5,6,7,6,2]<\/code>. So final array will contain only unique elements,Final array we recieve is [1,2,3,4,5,6,7]<\/code>.
\n3) After we have got unique elements, we sort the array, so that we can pick elements with lease value first. We also make a Cummulative<\/code> sum<\/code> array<\/code> for the array, where any value at index returns the sum of elements from 0th<\/sup> index to current index. So cummulative sum array for above array will be [1,3,6,10,15,21,28}<\/code>.<\/p>\n
    \n
  • Lower Bound<\/em><\/strong> : Lower Bound of any element K<\/code> in array is the index at which value is less than or equal to K<\/code>, and value at it’s next index is greater than K<\/code>.
    \n4) Now we have to take care of capacity now, if we take lower<\/code> bound<\/code> of capacity X<\/code> in above array, we will find the number of elements whose sum is less than or equal to capacity X<\/code>, hence we print the index as our answer.<\/li>\n<\/ul>\n<\/blockquote>\n
    Examples<\/h3>\n
    \n
      \n
    • Lets assume given array is [7,6,3,4,2,3,6,2]<\/code> and capacity X<\/code> is 10<\/code>.<\/li>\n
    • We remove repeating elements from array, so that array contains only unique elements [7,6,3,4,2]<\/code>.<\/li>\n
    • We sort the above array in a non-decreasing order, making current array as [2,3,4,6,7]<\/code>.<\/li>\n
    • We create a cummulative sum array for the above array, which will be [2,5,9,13,20]<\/code>.<\/li>\n
    • As our capacity is 10<\/code>, so we find lower<\/code> bound<\/code> of 10<\/code> in sum array, that is 2<\/code>. Value at index 2<\/code> is 9<\/code> which is lower than capacity. As index 2<\/code> is 3rd<\/sup> element of array. So our answer is 3<\/code>. Thes sum 9<\/code> is sum of elements 2,3<\/code> and 4<\/code>.<\/li>\n<\/ul>\n<\/blockquote>\n
      Solutions<\/h3>\n\t\t\t\t\t\t