Aman and Shopping

Last Updated on March 23, 2022 by Ria Pathak

Concepts Used

Sorting

Difficulty Level

Easy

Problem Statement (Simplified):

For a given array A, find the total number of elements you can pick in given capacity X. You can’t pick any item twice.

Test case

Input:
1
5 10
7 6 3 4 2

Output:
3

Explanation:
We 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.

See original problem statement here

Solving Approach :

Bruteforce Approach:

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.
2) 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.
3) 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.

Efficient Approach:

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.
2) 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]. So final array will contain only unique elements,Final array we recieve is [1,2,3,4,5,6,7].
3) 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 sum array for the array, where any value at index returns the sum of elements from 0^th index to current index. So cummulative sum array for above array will be [1,3,6,10,15,21,28}.

• Lower Bound : Lower Bound of any element K in array is the index at which value is less than or equal to K, and value at it’s next index is greater than K.
  4) Now we have to take care of capacity now, if we take lower bound of capacity X in above array, we will find the number of elements whose sum is less than or equal to capacity X, hence we print the index as our answer.

Examples

• Lets assume given array is [7,6,3,4,2,3,6,2] and capacity X is 10.
• We remove repeating elements from array, so that array contains only unique elements [7,6,3,4,2].
• We sort the above array in a non-decreasing order, making current array as [2,3,4,6,7].
• We create a cummulative sum array for the above array, which will be [2,5,9,13,20].
• As our capacity is 10, so we find lower bound of 10 in sum array, that is 2. Value at index 2 is 9 which is lower than capacity. As index 2 is 3^rd element of array. So our answer is 3. Thes sum 9 is sum of elements 2,3 and 4.

Solutions

#include <stdio.h>
#include<stdlib.h>

int compare(const void * a, const void * b) 
{ 
    return ( *(int*)a - *(int*)b ); 
} 

int lowerBound(int arr[],int start,int end,int key){
    int mid = (start+end)/2;
    if(start>end)
      return start;
    if(arr[mid]==key)
      return mid;
    if(arr[mid]>key)
      return lowerBound(arr,start,mid-1,key);
    else
      return lowerBound(arr,mid+1,end,key);
}

int main()
{
 int t;
 scanf("%d",&t);

 while(t--){

   int n, x;
   scanf("%d %d",&n,&x);

   int len = 0;

   int arr[100000]={0};
   int hash[99999] = {0};

   for(int i=0; i<n; i++){

     int temp;
      scanf("%d",&temp);

     if(hash[temp]==0){
      arr[len++] = temp;
      hash[temp]++;
     }
   }

  qsort((void*)arr, len, sizeof(arr[0]), compare); 
  // sort(arr,arr+len);

  for(int i=1; i<len;i++)
    arr[i]+=arr[i-1];

  int value = lowerBound(arr,0,len,x);

  if(x>arr[len-1])
    printf("%d\n",len);  
  else if(arr[value]==x)
    printf("%d\n",value+1);
  else
    printf("%d\n",value);

 }
}

#include <bits/stdc++.h>
using namespace std;

int lowerBound(int arr[],int start,int end,int key){
    int mid = (start+end)/2;
    if(start>end)
      return start;
    if(arr[mid]==key)
      return mid;
    if(arr[mid]>key)
      return lowerBound(arr,start,mid-1,key);
    else
      return lowerBound(arr,mid+1,end,key);
}

int main()
{
 int t;
 cin>>t;

 while(t--){

   int n, x;
   cin>>n>>x;

   int len = 0;

   int arr[100000]={0};
   int hash[99999] = {0};

   for(int i=0; i<n; i++){

     int temp;
     cin>>temp;

     if(hash[temp]==0){
      arr[len++] = temp;
      hash[temp]++;
     }
   }

   sort(arr,arr+len);

  for(int i=1; i<len;i++)
    arr[i]+=arr[i-1];

  int value = lowerBound(arr,0,len,x);

  if(x>arr[len-1])
    cout<<len<<endl;  
  else if(arr[value]==x)
    cout<<value+1<<endl;
  else
    cout<<value<<endl;
 }
}

Space Complexity
O(N) space is taken to maintain a Hash Array.

[forminator_quiz id="1335"]

In this blog, we have tried to explain the concept of sorting. If you want to solve more questions on Sorting, which are curated by our expert mentors at PrepBytes, you can follow this link Sorting practice