Maximum Books

Concepts Used

Heap

Difficulty Level

Medium

Problem Statement :

We are given N book costs, and k amount of money. We need to find the maximum number of books we can buy with the amount k.

See original problem statement here

Solution Approach :

Introduction :

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.
If the sum is greater than k, print the number of books we have bought.

Method 1:

  • We need to buy maximum number of books which is only possible if we buy books with least prices. If we have k 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 and also keep a counter variable to store the number of books we have bought.

  • Now when price-k<=0, we stop and print the books count.

  • We need to geneate a min heap of size N to get the least price every time we buy a book.

  • In a min-heap, the root always stores the smaller value as compared to its left & right 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.

  • Insert the cost of the books in the heap. Now extract the costs, add them to S & also keep track of the number of books we are buying.

  • Once S is greater than k print the number of books.

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

heapify(): 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), than the node.

Below is the algorithm of above approach according to the fundamentals of data structures in c++.

Algorithms :

Insert() :

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

Extract() :

  1. Store the value of the first node of our heap ( temp = heap[0] ).
  2. Replace the root node with the farthest right node (last element).
  3. Decrease the size by 1. (heap[0] = heap[size-1])
  4. Perform heapify starting from the new root.
  5. Return the stored value.(temp)

Heapify () :

  1. if the heap property holds true then you are done.
  2. else if
  3. the replacement node value <= its parent nodes value
    then swap them, and repeat step 3.
  4. else
  5. swap the replacement node with the smallest child node, and
    repeat step 3.

Example:

Solutions:

#include <stdio.h>
int parent(int i)
{
return (i-1)/2;
}
int left(int i)
{
return (i*2)+1;

}
int right(int i)
{
return (i*2)+2;
}
void swap(int *a,int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void insert(int heap[],int *size, int val)
{
heap[*size] = val;
int i = *size;
(*size)++;
while(i!=0 && heap[parent(i)]>heap[i])
{
swap(&heap[parent(i)],&heap[i]);
i = parent(i);
}

}
void heapify(int heap[],int i,int size)
{
int l = left(i);
int r = right(i);
int s = i;
if(l<size && heap[l]<heap[i])
s = l;
if(r<size && heap[r]<heap[s])
s = r;
if(s!=i)
{
swap(&heap[i],&heap[s]);
heapify(heap,s,size);
}

}
int extract(int heap[],int *size)
{
int root = heap[0];
heap[0] = heap[(*size)-1];
(*size)--;
heapify(heap,0,*size);
return root;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,k;
scanf("%d %d", &n,&k);
int *heap = (int *)malloc(sizeof(int)*n);
int size = 0;
for(int i=0;i<n;i++)
     {
     int t;
     scanf("%d",&t);
     insert(heap,&size,t);
     }
     int count=0,sum=0;

while(k>=0 && size)
{
     k -= extract(heap,&size);
     count++;
}
printf("%d\n",count-1);

}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int parent(int i)
{
     return (i-1)/2;
}
int left(int i)
{
     return (i*2)+1;
}
int right(int i)
{
     return (i*2)+2;
}
void swap(int *a,int *b)
{
     int temp = *a;
     *a = *b;
     *b = temp;
}
void insert(int heap[],int *size, int val)
{
     heap[*size]= val;
     int i = *size;
     (*size)++;
     while(i!=0 && heap[parent(i)]>heap[i])
     {
     swap(&heap[parent(i)],&heap[i]);
     i = parent(i);
     }
}
void heapify(int heap[],int i,int size)
{
     int l = left(i);
     int r = right(i);
     int s = i;
     if(l<size && heap[l]<heap[i])
        s = l;
     if(r<size && heap[r]<heap[s])
        s = r;
     if(s!=i)
     {
     swap(&heap[i],&heap[s]);
     heapify(heap,s,size);
     }
}
int extract(int heap[],int *size)
{
     int root = heap[0];
     heap[0] = heap[*size-1];
     (*size)--;
     heapify(heap,0,*size);
     return root;
}
 int main()
 {
   int t;
   cin>>t;
   while(t--)
   {
   int n,k;
   cin>>n>>k;
   int *heap = (int *)malloc(sizeof(int)*n);
   int size = 0;
   for(int i=0;i<n;i++)
   {
   int t;
   cin>>t;
   insert(heap,&size,t);
   }
   int count=0,sum=0;

   while(k>=0 && size)
   {
   k -= extract(heap,&size);
   count++;
   }
   cout<<count-1<<endl;

   }
   return 0;
 }
import java.util.*;
import java.io.*;
public class Main { 
     private int[] Heap; 
     private int size; 
     private int maxsize; 
     private static final int FRONT = 1; 
     public Main(int maxsize) 
     { 
          this.maxsize = maxsize; 
          this.size = 0; 
          Heap = new int[this.maxsize + 1]; 
          Heap[0] = Integer.MIN_VALUE; 
     } 
     private int parent(int pos) 
     { 
          return pos / 2; 
     } 
     private int leftChild(int pos) 
     { 
          return (2 * pos); 
     } 
     private int rightChild(int pos) 
     { 
          return (2 * pos) + 1; 
     } 
     // Function that returns true if the passed 
     // node is a leaf node 
     private boolean isLeaf(int pos) 
     { 
          if (pos >= (size / 2) && pos <= size) { 
               return true; 
          } 
          return false; 
     } 
     // Function to swap two nodes of the heap 
     private void swap(int fpos, int spos) 
     { 
          int tmp; 
          tmp = Heap[fpos]; 
          Heap[fpos] = Heap[spos]; 
          Heap[spos] = tmp; 
     } 
     // Function to heapify the node at pos 
     private void minHeapify(int pos) 
     { 
          // If the node is a non-leaf node and greater 
          // than any of its child 
          if (!isLeaf(pos)) { 
               if (Heap[pos] > Heap[leftChild(pos)] 
                    || Heap[pos] > Heap[rightChild(pos)]) { 
                    // Swap with the left child and heapify 
                    // the left child 
                    if (Heap[leftChild(pos)] < Heap[rightChild(pos)]) { 
                         swap(pos, leftChild(pos)); 
                         minHeapify(leftChild(pos)); 
                    } 
                    // Swap with the right child and heapify 
                    // the right child 
                    else { 
                         swap(pos, rightChild(pos)); 
                         minHeapify(rightChild(pos)); 
                    } 
               } 
          } 
     } 
     // Function to insert a node into the heap 
     public void insert(int element) 
     { 
          if (size >= maxsize) { 
               return; 
          } 
          Heap[++size] = element; 
          int current = size; 
          while (current != 1 && Heap[current] < Heap[parent(current)]) { 
               swap(current, parent(current)); 
               current = parent(current); 
          } 
     } 
     public int remove() 
     { 
          int popped = Heap[FRONT]; 
          Heap[FRONT] = Heap[size--]; 
          minHeapify(FRONT); 
          return popped; 
     } 
     // Driver code 
     public static void main(String[] arg) 
     { 
     Scanner sc = new Scanner(System.in);
     int t = sc.nextInt();
     while(t-->0)
     {
     int n = sc.nextInt();
     int k = sc.nextInt();
     int []a = new int[n];
     Main minHeap = new Main(n); 
     for(int i=0;i<n;i++)
     {
          a[i] = sc.nextInt();
          minHeap.insert(a[i]);
     }

          int count=0,sum=0;

     while(k>=0)
     {
          k -= minHeap.remove();
          count++;
     }

          System.out.println(count-1); 
     }
     } 
}
Previous post Prizes
Next post Small String

Leave a Reply

Your email address will not be published. Required fields are marked *