HackerEarth Problem Link

I have solved this question by sorting the strength and using them in reverse order.

It seems sorting will increase time complexity.

Here is my Solution Link.

Help me to optimise this code.

HackerEarth Problem Link

I have solved this question by sorting the strength and using them in reverse order.

It seems sorting will increase time complexity.

Here is my Solution Link.

Help me to optimise this code.

I have not tried this but it may work.

Try to use bubble sort. in this algorithm we can get the largest element in 1st iteration and second greatest in 2nd iteration and so on. After each iteration you can add it to sum and check whether you achieved required strength. you need not sort the entire array but only as many times as the answer.

For worst case, your time comp will be O(n^2) but the above one is O(n Logn)

@sebastian @shivamjaiswal6

modified bubble sort

best time 0.505

for this sol 0.508

```
#include <stdio.h>
int main(){
int n,sum=0,s,i,j,temp,swapped,ind,finished=0;
scanf("%d", &n);
int arr[n];
for(i=0;i<n;i++)scanf("%d", &arr[i]);
scanf("%d", &s);
ind=n-1;
for(i=0;i<n-1;i++){
swapped=0;
for(j=0;j<n-i-1;j++){
if (arr[j] > arr[j+1]){
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
swapped=1;
}
}
if(!swapped)
break;
s-=arr[ind--];
if(s<=0){
finished=1;
break;
}
}
while(!finished){
s-=arr[ind--];
if(s<=0){
finished=1;
break;
}
}
printf("%d",n-ind-1);
return 0;
}
```

You made me try

1 Like

What is the exact time?

Bro, I was just asking the total time because I also made submission to see what time will it take if we sort. My time was 0.5086. But you are faster with 0.5084. Chill man

1 Like

oh

Wow!

The above approach really reduces the time.

Thanks for helping

#include<bits/stdc++.h>

using namespace std;

int main()

{

int n;

cin>>n;

vector a(n);

int i;

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

cin>>a[i];

sort(a.begin(),a.end());

int k;

cin>>k;

int c=0,s=0;

for(i=n-1;i>=0;i–)

{

s=s+a[i];

c++;

if(s>k)

break;

}

cout<<c<<endl;

return 0;

}