problem in chef and integer problem

#include
using namespace std;
int counting(long int[],unsigned long int);
int main()
{
unsigned long int n;
cin>>n;
long int* a=new long int[n];
for(int i=0;i<n;i++)
cin>>a[i];
unsigned long int x;
cin>>x;
int sum=0;
int count=0;
count=counting(a,n);
while(count>=x)
{
for(int i=0;i<n;i++)
a[i]=a[i]+1;
count=counting(a,n);
sum+=x;

}
for(int i=0;i<n;i++)
{
    if(a[i]<0)
        sum-=a[i];
}
cout<<sum;
}
 int counting(long int a[],unsigned long int n)
 {
int count=0;
for(int i=0;i<n;i++)
    if(a[i]<0)
    count++;
return count;
}

Ur algo will give the correct ans, but the problem is the time complexity…which is very large…go through the editorial of the problem to get an idea of the algo to be used to get an AC in the given timelimit…:slight_smile:

consider this case…there are 10^5 numbers in the array…each number is -10^9 and the variable “x” is also 10^5…ur algo will take ages to complete…as the outer while loop will run 10^5 times and the inner loop will run 10^9 times for each iteration of the while loop i.e. 10^5 * 10^9 which is way beyond the time limit…also the function that u have made will run 10^5 times which itself will run for 10^9 i.e. again 10^5 * 10^9…so ur complexity is very high…hope u understand y u r getting a tle…:slight_smile:

1 Like

The algorithm you are using is very inefficient as you make a lot of iterations over the array which is of size 10^5.
You should try to come up with a more efficient algorithm sorting the numbers and also neglecting positive numbers. If you sort the numbers you wont need to update and count every time.Come up with a better algorithm and ask me incase you need more help.

i think u mean to say neglecting +ve numbers…:stuck_out_tongue:

1 Like

Probably you can go through this blog http://vivekky93.blogspot.in/ where the author try to explain how to reach to answer and how you can judge which code works.

//