[Solved] Find total number of (i,j) pairs in an array such that i

by


Problem: find (i,j), i<j, s.t. a[i] + a[j] = i + j

I propose the following approach:

  1. Set b[i] = a[i] - i
    The problem becomes: find (i,j), i<j, s.t. b[i] + b[j] = 0
    Complexity: O(n)

  2. Create objects c[i] = (b[i],i), a struct for example, in a std::vector (or std::array)
    Complexity: O(n)

  3. Sort the c[i] pairs according to b values -> get d[j] = (v[j], i[j]) , sorted array
    Complexity: O(nlogn)

  4. Find all pairs j,k such that v[j] = -v[k]
    Complexity: the array being sorted, should be O(n)

  5. keep the cases i[j] < i[k]
    Complexity: O(n)

3

solved Find total number of (i,j) pairs in an array such that i