Given an array A[] of N integers, the task is to calculate the total number of pairs of indices (i, j) satisfying the following conditions –
- 1 ? i < j ? N
- minimum(A[i], A[j]) = i
- maximum(A[i], A[j]) = j
Note: 1-based indexing is considered.
Examples:
Input: N = 4, A[] = {1, 3, 2, 4}
Output: 2
Explanation: First pair of indices is (1, 4),
As minimum(A[1], A[4]) = minimum(1, 4) = 1 and
maximum(A[1], A[4]) = maximum(1, 4) = 4.
Similarly, second pair is (3, 2).Input: N = 10, A[] = {5, 8, 2, 2, 1, 6, 7, 2, 9, 10}
Output: 8
Approach: The problem can be solved based on the following idea:
The conditions given in the problem would be satisfied, if one of these two conditions holds :
- 1st Type: A[i] = i and A[j] = j
- 2nd Type: A[i] = j and A[j] = i
Say there are K such indices where A[i] = i. So, number of pairs satisfying the first condition is K * (K – 1) / 2.
The number of pairs satisfying the second condition can be simply counted by traversing through the array.
i.e., checking if A[i] ? i and A[A[i]] = i.
Follow the steps mentioned below to implement the idea:
- Traverse through the array and find the position where the value and the position are same (say K).
- Find the pairs of the first type mentioned above using the provided formula.
- Now traverse again using and find the second type of pair following the mentioned method.
Below is the implementation of this approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to count Number of pairs in// array satisfying the given conditionsint countPairs(int N, int A[]){ // Variable to store the number of indices such // that their value is equal to their position int count = 0; // Variable to store the total number of pairs // following the given condition int answer = 0; for (int i = 0; i < N; i++) { if (A[i] == (i + 1)) { count++; } } // Pairs following the first condition answer += count * (count - 1) / 2; // Calculating number of pairs following // the second condition for (int i = 0; i < N; i++) { if (A[i] > (i + 1) && A[A[i] - 1] == (i + 1)) { answer++; } } // Returning answer return answer;}// Driver Codeint main(){ int N = 4; int A[] = { 1, 3, 2, 4 }; // Function call int answer = countPairs(N, A); cout << answer << endl; return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { // Function to count Number of pairs in // array satisfying the given conditions static int countPairs(int N, int A[]) { // Variable to store the number of indices such // that their value is equal to their position int count = 0; // Variable to store the total number of pairs // following the given condition int answer = 0; for (int i = 0; i < N; i++) { if (A[i] == (i + 1)) { count++; } } // Pairs following the first condition answer += count * (count - 1) / 2; // Calculating number of pairs following // the second condition for (int i = 0; i < N; i++) { if (A[i] > (i + 1) && A[A[i] - 1] == (i + 1)) { answer++; } } // Returning answer return answer; } public static void main (String[] args) { int N = 4; int A[] = { 1, 3, 2, 4 }; // Function call int answer = countPairs(N, A); System.out.println(answer); }}// This code is contributed by aadityapburujwale |
Python3
# Python3 code for the above approach# Function to count Number of pairs# in array satisfying the given conditionsdef countpairs(n,a)->int: # Variable to store the number of indices # such that their value is equal to their position count = 0 # Variable to store the total number # of pairs following the given condition answer = 0 for i in range(0,n): if(a[i] == i+1): count += 1 # Pairs following the first condition answer += ((count)*(count-1))//2 # Calculating number of pairs following the second condition for i in range(0,n): if(a[i] > (i+1) and a[a[i]-1] == (i+1)): answer += 1 # Returning answer return answer# Driver Codeif __name__ == '__main__': n = 4 a = [1,3,2,4] # Function call ans = countpairs(n,a) print(ans) # This code is contributed by ajaymakvana. |
C#
// C# program for above approachusing System;class GFG{ // Function to count Number of pairs in // array satisfying the given conditions static int countPairs(int N, int[] A) { // Variable to store the number of indices such // that their value is equal to their position int count = 0; // Variable to store the total number of pairs // following the given condition int answer = 0; for (int i = 0; i < N; i++) { if (A[i] == (i + 1)) { count++; } } // Pairs following the first condition answer += count * (count - 1) / 2; // Calculating number of pairs following // the second condition for (int i = 0; i < N; i++) { if (A[i] > (i + 1) && A[A[i] - 1] == (i + 1)) { answer++; } } // Returning answer return answer; }// Driver Codepublic static void Main(){ int N = 4; int[] A = { 1, 3, 2, 4 }; // Function call int answer = countPairs(N, A); Console.Write(answer);}}// This code is contributed by code_hunt. |
Javascript
<script>// Javascript code for the above approach// Function to count Number of pairs in// array satisfying the given conditionsfunction countPairs( N,A){ // Variable to store the number of indices such // that their value is equal to their position let count = 0; // Variable to store the total number of pairs // following the given condition let answer = 0; for (let i = 0; i < N; i++) { if (A[i] == (i + 1)) { count++; } } // Pairs following the first condition answer += count * (count - 1) / 2; // Calculating number of pairs following // the second condition for ( let i = 0; i < N; i++) { if (A[i] > (i + 1) && A[A[i] - 1] == (i + 1)) { answer++; } } // Returning answer return answer;}// Driver Code let N = 4; let A = [ 1, 3, 2, 4 ]; // Function call let answer = countPairs(N, A); document.write(answer); // This code is contributed by satwik4409. </script> |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
