#### 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. So, we follow this approach by referring the best online programming courses.

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 of any elementLower Bound`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`

.