Alternative to nested for loop

[suksham]

Hello Friends ... please help me to prevent runtime error in following code:
#include<iostream>

using namespace std;

long long int t =0;

main()
{
long long int n,k;
cin>>n>>k;
t =n;
long long int hard[t];
for(int i=0; i<n; i++)
{
cin>>hard[i];
}
long long int s=0;
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
if(hard[i] + hard[j] < k)
{
s++;
}
}
}
cout<<s;
return 0;
}

Is there any alternative to replace nested for loops ... as its also affecting time complexity of the program..

Thank You
Regards
Suksham Kapuria
Std XII
Chandigarh, India

[doug4]

By the way, this line should not be legal:

long long int hard[t];

You are not allowed to create an array of unknown size on the stack. You should dynamically allocate it, or better yet, use an STL container, like a std::vector.

Also, please use code tags in your posts. Edit your post, highlight the code, and click the "<>" Format button. You can also add [ code ] and [ /code ] (without the spaces) before and after your code if the Format button does not work.


If your goal is to compare all elements of an array with all subsequent elements of an array, you will have complexity of n^2.

It looks like you are trying to figure out how many pairs of number in your array have a sum smaller than 'k'. If you had a sorted array, you might be able to make some assumptions about lesser values, but sorting (worst case) will be at least n log(n) and comparison (worst case) would still be n^2. So, I don't think you can improve much on your algorithm.