# Variety of pairs of Array the place the max and min of pair is identical as their indices

0
11 Given an array A[] of N  integers, the duty is to calculate the whole variety of pairs of indices (i, j) satisfying the next situations –

• 1 ≤ i < j ≤ N
• minimal(A[i], A[j]) = i
• most(A[i], A[j]) = j

Notice: 1-based indexing is taken into account.

Examples:

Enter: N = 4, A[] = {1, 3, 2, 4}
Output: 2
Clarification: First pair of indices is (1, 4),
As minimal(A, A) = minimal(1, 4) = 1 and
most(A, A) = most(1, 4) = 4.
Equally, second pair is (3, 2).

Enter: N = 10, A[] = {5, 8, 2, 2, 1, 6, 7, 2, 9, 10}
Output: 8

Method: The issue may be solved primarily based on the next concept:

The situations given in the issue can be happy, if one in every of these two situations holds :

• 1st Kind: A[i] = i and A[j] = j
• 2nd Kind: A[i] = j and A[j] = i

Say there are Okay such indeices the place A[i] = i. So, variety of pairs satisfying the primary situation is Okay * (Okay – 1) / 2.
The variety of pairs satisfying the second situation may be merely counted by traversing by means of the array.
i.e., checking if A[i] ≠ i and A[A[i]] = i.

Comply with the steps talked about beneath to implement the thought:

• Traverse by means of the array and discover the place the place the worth and the place are identical (say Okay).
• Discover the pairs of the primary kind talked about above utilizing the offered method.
• Now traverse once more utilizing and discover the second kind of pair following the talked about technique.

Beneath is the implementation of this method:

## C++

 ` `  `#embrace ` `utilizing` `namespace` `std;` ` `  `int` `countPairs(``int` `N, ``int` `A[])` `{` `    ` `    ` `    ``int` `rely = 0;` ` `  `    ` `    ` `    ``int` `reply = 0;` ` `  `    ``for` `(``int` `i = 0; i < N; i++) {` `        ``if` `(A[i] == (i + 1)) {` `            ``rely++;` `        ``}` `    ``}` ` `  `    ` `    ``reply += rely * (rely - 1) / 2;` ` `  `    ` `    ` `    ``for` `(``int` `i = 0; i < N; i++) {` `        ``if` `(A[i] > (i + 1) && A[A[i] - 1] == (i + 1)) {` `            ``reply++;` `        ``}` `    ``}` ` `  `    ` `    ``return` `reply;` `}` ` `  `int` `primary()` `{` `    ``int` `N = 4;` `    ``int` `A[] = { 1, 3, 2, 4 };` ` `  `    ` `    ``int` `reply = countPairs(N, A);` `    ``cout << reply << endl;` `    ``return` `0;` `}`

Time Complexity: O(N)
Auxiliary Area: O(1)