CODEWITHSUNDEEP
c++arraysalgorithmsorting
Abhishek Jha
Abhishek Jha

Reputation: 61

Find indices i<j in an array of size n so that the sum of values at those indices is equal to i + j

My solution : 

#include <bits/stdc++.h>

int main() {
    int n;//Size of array
    std::cin>>n;
    std::vector<long long>vec_int;
    int temp = n;
    while(n--){
        long long k ;
        std::cin>>k;
        vec_int.push_back(k);
    }
    n = temp;
    int num = 0;
    for(int  i = 0 ; i < n-1 ; i++){
        for(int j = i+1; j<n; j++){
            if(i<j && i+j == vec_int[i]+vec_int[j])
                num++;
        }
    }

    std::cout<<num;

    return 0;
}

I am scanning the array which takes about O(n^2) time. On very large arrays the time limit for the question exceeds the 2s duration. I tried sorting the array but didn't get too far. How can I speed this up? Is it possible to do this in O(n) time complexity.

Upvotes: 2

Views: 158

Answers (1)

zch
zch

Reputation: 15278

Consider redefinition of your problem. The expression:

i+j == vec_int[i]+vec_int[j]

is algebraically equivalent to:

vec_int[i] - i == -(vec_int[j] - j)

So define:

a[i] = vec_int[i] - i

And now the question is to count how many times a[i] == -a[j].

This can be tested in O(n). Use unordered_map m to count how many times each negative value is present in a. Then for each positive value a[i] will be paired with m[-a[i]] negative values. Also count number of zeroes in a and compute number of pairs between those.

Upvotes: 6

Related Questions