Wednesday, August 3, 2022
HomeWordPress DevelopmentVariety of pairs of Array the place the max and min of...

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


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

 

Strategy: The issue might be solved based mostly on the next concept: 

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

  • 1st Sort: A[i] = i and A[j] = j
  • 2nd Sort: 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 might be merely counted by traversing via 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 via the array and discover the place the place the worth and the place are similar (say Okay).
  • Discover the pairs of the primary kind talked about above utilizing the supplied method.
  • Now traverse once more utilizing and discover the second kind of pair following the talked about technique.

Under 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 fundamental()

{

    int N = 4;

    int A[] = { 1, 3, 2, 4 };

  

    

    int reply = countPairs(N, A);

    cout << reply << endl;

    return 0;

}

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

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments