Find pairs

3.8

27 votes
Basic Programming
Problem

Given an array \(A\) of length \(N\). Find the number of ordered pairs \((i, j)\) which satisfy the given condition

  • \((A[i] - A[j]) / (i - j) = 1\)
  • \(A[i] - A[j]\) should be divisible by \(i-j\)
  • \(i \neq j\)

Input format

  • The first line contains an integer \(N\).
  • The second line of each test case contains \(N\) space-separated integers, denoting the elements of array \(A\).

Output format

Print the number of ordered pairs (i, j) which satisfy the above condition in a new line.

Constraints

\(1 \le N \le 5 \times 10 ^ 5 \\ 1 \le A[i] \le 10^6\)

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For every pair \((i, j)\) in this array where \(i \neq j\), it satisfy the condition in the problem statement. Hence, the answer is 6.

Editor Image

?