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[1], A[4]) = minimal(1, 4) = 1 and 
most(A[1], A[4]) = 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 <bits/stdc++.h>

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)

LEAVE A REPLY

Please enter your comment!
Please enter your name here