Need better Approach

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. :thinking:
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. :slightly_smiling_face:

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 :sweat_smile:

1 Like

What is the exact time? :upside_down_face:

@sebastian You don’t trust me :triumph: here is the link to the submission :wink:

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 :grimacing:

1 Like

oh :sweat_smile:

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;
}

1 Like