Answer to Question #229127 in C++ for Asjad

Question

Harry loves numbers in the range [m1, m2] (m1 and m2 included). carry decides to gift harry an array of numbers for his birthday. harry wants to find the number of pairs of indices [l, r] for which the sum of all the elements in the range [l, r] lies between m1 and m2.

Come up with an algorithm with a worst case complexity of O(N2).

Now improvise this algorithm, assuming all numbers are positive integers.

What if the numbers could be negative as well? Can you think of an O(nlogn) solution in this case? (Hint: use sorting)

Answer 1

// corecudr
#include <iostream>

using namespace std;

int n, m1, m2, gift[100], ans = 0;

int main()
{
    cin >> n >> m1 >> m2;
    for (int i = 0; i < n; i++) cin >> gift[i];
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (i != j && gift[i]+gift[j]<=m2 && gift[i]+gift[j]>=m1) ans++;
        }
    }
    cout << ans;

    return 0;
}
Sample Input 1:
5
7 15
2 3 5 10 9
Sample Output 1:
8