  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Aman and Shopping Sorting

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 0th 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 3rd 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={0};
int hash = {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), 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={0};
int hash = {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