HackerEarth Array Modification problem solution

In this HackerEarth Array Modification problem solution, You are given an array A of N integers. For every index i of the array A, you need to select an index j such that j != i and the product of A[i] and A[j] is maximum for that i. Finally, you need to print the sum of A[i] * A[j] for all the indices i. Since this sum can be large, you need to print it to the modulo 10^9 + 7.

Note: Please refer to the sample explanation section.

HackerEarth Array Modification problem solution.

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){ a%=m;LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
LL a[100001];
LL ans[100001];int main()   {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    assert(cin >> n);
    assert(n >= 1 && n <= 100000);
    for(int i = 1; i <= n; i++) {
        assert(cin >> a[i]);
        assert(a[i] >= -1000000000000000000LL && a[i] <= 1000000000000000000LL);
    }
    vector<LL> positive, negative;
    for(int i = 1; i <= n; i++) {
        if(a[i] >= 0) {
            positive.push_back(a[i]);
        }   
        else {
            negative.push_back(a[i]);
        }
    }
    sort(positive.begin() , positive.end());
    sort(negative.begin(), negative.end(), greater<LL>());
    int positive_cnt = positive.size();
    int negative_cnt = negative.size();
    for(int i = 1; i <= n; i++) {
        if(a[i] == 0) {
            ans[i] = 0;
        }
        else if(a[i] < 0) {
            if(negative.size() == 1) {
                ans[i] = (a[i] % M) * (positive[0] % M);
            }
            else{
                if(negative.back() == a[i])
                    ans[i] = (a[i] % M) * (negative[negative_cnt - 2] % M);
                else
                    ans[i] = (a[i] % M) * (negative.back() % M);
            }
        }
        else {
            if(positive.size() == 1) {
                ans[i] = (a[i] % M) * (negative[0] % M);
            }
            else{
                if(positive.back() == a[i])
                    ans[i] = (a[i] % M) * (positive[positive_cnt - 2] % M);
                else
                    ans[i] = (a[i] % M) * (positive.back() % M);
            }
        }
        ans[i] %= M;
        if(ans[i] < M)
            ans[i] += M;
    }
    LL final_answer = 0;
    for(int i = 1; i <= n; i++) {
        final_answer += ans[i];
        final_answer %= M;
    }
    cout << final_answer;
}

HackerEarth Array Modification problem solution.

Leave a Reply