{"id":1674,"date":"2020-07-01T09:29:58","date_gmt":"2020-07-01T09:29:58","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1674"},"modified":"2022-03-29T09:59:10","modified_gmt":"2022-03-29T09:59:10","slug":"maximum-books","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/maximum-books\/","title":{"rendered":"Maximum Books"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Heap<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

We are given N<\/code> book costs, and k<\/code> amount of money. We need to find the maximum number of books we can buy with the amount k<\/code>.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

In order to buy maximum number of books we have to buy the books with lesser price first. We will sum up the costs of the books we have bought.
\nIf the sum is greater than k<\/code>, print the number of books we have bought.<\/p>\n<\/blockquote>\n

Method 1:<\/h4>\n
    \n
  • \n

    We need to buy maximum number of books which is only possible if we buy books with least prices. If we have k<\/code> amount of money we can sort the prices in increasing order, now we starting buying books and subtracting the prices of the books we bought from k<\/code> and also keep a counter variable to store the number of books we have bought. <\/p>\n<\/li>\n

  • \n

    Now when price-k<=0<\/code>, we stop and print the books count.<\/p>\n<\/li>\n

  • \n

    We need to geneate a min heap of size N<\/code> to get the least price every time we buy a book.<\/p>\n<\/li>\n

  • \n

    In a min-heap<\/strong>, the root always stores the smaller value as compared to its left<\/strong> & right<\/strong> subtree, this condition needs to be true for every node. We need to insert each item one by one such that parent is always smaller than the item itself. If parent is greater, then swap the current item with its parent. <\/p>\n<\/li>\n

  • \n

    Insert<\/strong> the cost of the books in the heap. Now extract<\/strong> the costs, add them to S<\/code> & also keep track of the number of books we are buying.<\/p>\n<\/li>\n

  • \n

    Once S<\/code> is greater than k<\/code> print the number of books.<\/p>\n<\/li>\n<\/ul>\n

    extract()<\/strong>: Removes the minimum element from Min-Heap<\/strong>. Time Complexity of this Operation is O(Logn) as this operation needs to maintain the heap property (by calling heapify()<\/strong>) after removing root.<\/p>\n

    heapify()<\/strong>: Maintains the heap property for each node. If any node does not follow heap property it swaps the node with the node which is smaller ,or greater (in case of max-heap<\/strong>), than the node.<\/p>\n

    Below is the algorithm of above approach.<\/p>\n

    Algorithms :<\/h3>\n

    Insert() :<\/h4>\n
    \n
      \n
    1. Insert the item at the last index, and increment the size by 1.<\/li>\n
    2. Then, check if the inserted item is smaller than its parent,<\/li>\n
    3. If yes, then swap the inserted item with its parent.<\/li>\n
    4. If no, then do nothing.<\/li>\n
    5. Now, go to step 2<\/code> and repeat untill we reach root (first element).<\/li>\n<\/ol>\n<\/blockquote>\n

      Extract() :<\/h4>\n
      \n
        \n
      1. Store the value of the first node of our heap ( temp = heap[0]<\/code> ).<\/li>\n
      2. Replace the root node with the farthest right node (last element).<\/li>\n
      3. Decrease the size by 1<\/code>. (heap[0] = heap[size-1])<\/code><\/li>\n
      4. Perform heapify<\/strong> starting from the new root. <\/li>\n
      5. Return the stored value.(temp<\/strong>)<\/li>\n<\/ol>\n<\/blockquote>\n

        Heapify () :<\/h4>\n
        \n
          \n
        1. if the heap property holds true then you are done.<\/li>\n
        2. else if<\/li>\n
        3. the replacement node value <= its parent nodes value
          \nthen swap them, and repeat step 3.<\/li>\n
        4. else<\/li>\n
        5. swap the replacement node with the smallest child node, and
          \nrepeat step 3.<\/li>\n<\/ol>\n<\/blockquote>\n

          Example:<\/h4>\n

          \"\"<\/p>\n

          Solutions:<\/h3>\n\t\t\t\t\t\t