2
\$\begingroup\$

The question is: To select 2 numbers out of n positive integer inputs (order matters), where the number that is placed anywhere before the second must be greater than the second by a given number m. Count the total number of selections.

An example answer would be, given the inputs 5 1 3 2 4 and m is 0, the total number of selections is 5 (51,53,52,54,32)

Another example answer would be, given the inputs 6 5 4 3 2 1 and m is 2, the total number of selections is 6 (63,62,61,52,51,41)

How do I improve my double for-loop method in terms of time?

using namespace std;

int main()
{
    int n, m, i, j, m = 0, sum = 0;
    cin >> n >> m;
    int *a=new int[n];
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
        
    for(i=0;i<n-1;i++)
    {
        if (a[i] - m <= 0)  continue;
        int temp=a[i]-m;
        for(j=i+1;j<n;j++)
        if(a[j]<temp) sum++;
    }
    cout<<sum<<endl;
    return 0;
}
`
\$\endgroup\$
3
  • \$\begingroup\$ Think of counting inversions. The approach is the same, with a slight modification. \$\endgroup\$ Commented Dec 30, 2020 at 17:56
  • \$\begingroup\$ The results of your second example seems to be missing 64, 53, 42 and 31 \$\endgroup\$ Commented Dec 31, 2020 at 18:25
  • \$\begingroup\$ No, it has to be strictly greater than 2. \$\endgroup\$ Commented Jan 2, 2021 at 14:44

2 Answers 2

Reset to default
2
\$\begingroup\$ 
using namespace std;

Don't do this. We have namespaces for a reason, you know. And we seem to be missing the necessary Standard Library headers <iostream> and <cstdio>.

    int n, m, i, j, m = 0, sum = 0;

These variable names tell us nothing about what they are used for. Please use more expressive names.

    cin >> n >> m;

When reading from a stream such as std::cin, it's vital to check that the conversion was successful before using the values. That could be as simple as

if (!cin) {
    return EXIT_FAILURE;
}

    int *a=new int[n];

Prefer a standard container (e.g. std::vector).

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

If we had a std::vector, we could have avoided hand-coding this loop:

auto a = std::vector{};
a.reserve(n);
std::copy_n(std::istream_iterator<int>(std::cin), n, a.begin());

        scanf("%d", &a[i]);

Why are we mixing C++ streams and C stdio? It's better to use just one (preferably the streams). Again, we're missing the test whether the conversion was successful.

\$\endgroup\$
0
\$\begingroup\$

Thanks to vnp's comment about counting inversions! This link should be fully sufficient to optimize your code with a modified merge sort scheme:

https://towardsdatascience.com/basic-algorithms-counting-inversions-71aaa579a2c0

As far as I can see, the only thing you'll have to modify is this line

if array[i] > array[j]

with your desired delta value m.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.