Given an integer N and an array arr[] that contains elements in the range [1, N], the task is to find the count of all pairs (arr[i], arr[j]) such that i < j and i == arr[j] and j == arr[i].
Input: N = 4, arr[] = {2, 1, 4, 3}
Output: 2
Explanation:
All possible pairs are {1, 2} and {3, 4}
Input: N = 5, arr[] = {5, 5, 5, 5, 1}
Output: 1
Explanation:
Only possible pair: {1, 5}
Naive Approach:
The simplest approach is to generate all possible pairs of the given array and if any pair satisfies the given condition, increase count. Finally, print the value of count.
C++
#include <bits/stdc++.h>
using namespace std;
void countPairs( int N, int arr[])
{
int count = 0;
for ( int i = 0; i < N - 1; i++) {
for ( int j = i + 1; j < N; j++) {
if ((i + 1) == arr[j] && (j + 1) == arr[i])
count++;
}
}
cout << count << endl;
}
int main()
{
int arr[] = { 5, 5, 5, 5, 1 };
int N = sizeof (arr) / sizeof (arr[0]);
countPairs(N, arr);
}
|
Java
import java.util.Arrays;
public class Gfg {
public static void main(String[] args)
{
int [] arr = { 5 , 5 , 5 , 5 , 1 };
int N = arr.length;
int count = 0 ;
for ( int i = 0 ; i < N - 1 ; i++) {
for ( int j = i + 1 ; j < N; j++) {
if ((i + 1 ) == arr[j] && (j + 1 ) == arr[i])
count++;
}
}
System.out.println(count);
}
}
|
Python3
def countPairs(N, arr):
count = 0
for i in range (N - 1 ):
for j in range (i + 1 , N):
if (i + 1 ) = = arr[j] and (j + 1 ) = = arr[i]:
count + = 1
print (count)
if __name__ = = "__main__" :
arr = [ 5 , 5 , 5 , 5 , 1 ]
N = len (arr)
countPairs(N, arr)
|
C#
using System;
class Gfg
{
public static void Main( string [] args)
{
int [] arr = { 5, 5, 5, 5, 1 };
int N = arr.Length;
int count = 0;
for ( int i = 0; i < N - 1; i++)
{
for ( int j = i + 1; j < N; j++)
{
if ((i + 1) == arr[j] && (j + 1) == arr[i])
count++;
}
}
Console.WriteLine(count);
}
}
|
Javascript
function countPairs(N, arr)
{
let count = 0;
for (let i = 0; i < N - 1; i++) {
for (let j = i + 1; j < N; j++) {
if ((i + 1) == arr[j] && (j + 1) == arr[i])
count++;
}
}
console.log(count);
}
let arr = [ 5, 5, 5, 5, 1 ];
let N = arr.length;
countPairs(N, arr);
|
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach:
Follow the steps below to solve the above approach:
- Traverse the given array and keep the count of elements(say cnt) whose index equals to arr[arr[index] – 1] – 1. This will count the valid pair with the given criteria.
- After traversal, the total count is given by cnt/2 as we have count every pair twice in the above traversal.
Below is the implementation of the above approach:
C++
#include<bits/stdc++.h>
using namespace std;
void countPairs( int N, int arr[])
{
int count = 0;
for ( int i = 0; i < N; i++)
{
if (i == arr[arr[i] - 1] - 1)
{
count++;
}
}
cout << (count / 2) << endl;
}
int main()
{
int arr[] = { 2, 1, 4, 3 };
int N = sizeof (arr)/ sizeof (arr[0]);
countPairs(N, arr);
}
|
Java
import java.util.*;
class GFG {
static void countPairs( int N, int [] arr)
{
int count = 0 ;
for ( int i = 0 ; i < N; i++) {
if (i == arr[arr[i] - 1 ] - 1 ) {
count++;
}
}
System.out.println(count / 2 );
}
public static void main(String[] args)
{
int [] arr = { 2 , 1 , 4 , 3 };
int N = arr.length;
countPairs(N, arr);
}
}
|
Python3
def countPairs(N, arr):
count = 0
for i in range (N):
if (i = = arr[arr[i] - 1 ] - 1 ):
count + = 1
print (count / / 2 )
if __name__ = = "__main__" :
arr = [ 2 , 1 , 4 , 3 ]
N = len (arr)
countPairs(N, arr)
|
C#
using System;
class GFG{
static void countPairs( int N, int [] arr)
{
int count = 0;
for ( int i = 0; i < N; i++)
{
if (i == arr[arr[i] - 1] - 1)
{
count++;
}
}
Console.Write(count / 2);
}
public static void Main( string [] args)
{
int [] arr = { 2, 1, 4, 3 };
int N = arr.Length;
countPairs(N, arr);
}
}
|
Javascript
<script>
function countPairs(N, arr)
{
let count = 0;
for (let i = 0; i < N; i++)
{
if (i == arr[arr[i] - 1] - 1)
{
count++;
}
}
document.write(count / 2);
}
let arr = [ 2, 1, 4, 3 ];
let N = arr.length;
countPairs(N, arr);
</script>
|
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us