Given an array A[]. The task is to determine if it is possible to choose two indices ‘i’ and ‘j’ such that the below conditions gets satisfied:-
- A[i] is not equal to A[j].
- A[A[i]] is equal to A[A[j]].
Note: The value of the elements in an array is less than the value of N i.e. For every i, arr[i] < N.
Examples:
Input: N = 4, A[] = {1, 1, 2, 3}
Output: Yes
As A[3] != to A[1] but A[A[3]] == A[A[1]]
Input: N = 4, A[] = {2, 1, 3, 3}
Output: No
As A[A[3]] == A[A[4]] but A[3] == A[4]
Approach:
- Start traversing the Array Arr[] by running two loops.
- The variable i point at the index 0 and variable j point to the next of i.
- If Arr[i] is not equal to Arr[j] then check if Arr[Arr[i] – 1] is equal to Arr[Arr[j] – 1]. If yes then return true.
Else check Arr[Arr[i]- 1] and Arr[Arr[j] – 1] for other indices also. - Repeat the above step till all the elements/index gets traversed.
- If no such indices found return false.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function that will tell whether// such Indices present or Not.bool checkIndices(int Arr[], int N){ for (int i = 0; i < N - 1; i++) { for (int j = i + 1; j < N; j++) { // Checking 1st condition i.e whether // Arr[i] equal to Arr[j] or not if (Arr[i] != Arr[j]) { // Checking 2nd condition i.e whether // Arr[Arr[i]] equal to Arr[Arr[j]] or not. if (Arr[Arr[i] - 1] == Arr[Arr[j] - 1]) return true; } } } return false;}// Driver Codeint main(){ int Arr[] = { 3, 2, 1, 1, 4 }; int N = sizeof(Arr) / sizeof(Arr[0]); // Calling function. checkIndices(Arr, N) ? cout << "Yes" : cout << "No"; return 0;} |
Java
// Java implementation of the above approach // Function that calculates marks. class GFG{ static boolean checkIndices(int Arr[], int N) { for (int i = 0; i < N - 1; i++) { for (int j = i + 1; j < N; j++) { // Checking 1st condition i.e whether // Arr[i] equal to Arr[j] or not if (Arr[i] != Arr[j]) { // Checking 2nd condition i.e whether // Arr[Arr[i]] equal to Arr[Arr[j]] or not. if (Arr[Arr[i] - 1] == Arr[Arr[j] - 1]) return true; } } } return false; } // Driver code public static void main(String args[]) { int Arr[] = { 3, 2, 1, 1, 4 }; int N = Arr.length; if(checkIndices(Arr, N)) System.out.println("Yes"); else System.out.println("No"); } } // This code is Contributed by // Naman_Garg |
Python 3
# Python 3 implementation of the # above approach# Function that will tell whether# such Indices present or Not.def checkIndices(Arr, N): for i in range(N - 1): for j in range(i + 1, N): # Checking 1st condition i.e whether # Arr[i] equal to Arr[j] or not if (Arr[i] != Arr[j]): # Checking 2nd condition i.e whether # Arr[Arr[i]] equal to Arr[Arr[j]] or not. if (Arr[Arr[i] - 1] == Arr[Arr[j] - 1]): return True return False# Driver Codeif __name__ == "__main__": Arr = [ 3, 2, 1, 1, 4 ] N =len(Arr) # Calling function. if checkIndices(Arr, N): print("Yes") else: print("No")# This code is contributed by ita_c |
C#
// C# implementation of the above approach using System;class GFG{ // Function that calculates marks. static bool checkIndices(int []Arr, int N) { for (int i = 0; i < N - 1; i++) { for (int j = i + 1; j < N; j++) { // Checking 1st condition i.e whether // Arr[i] equal to Arr[j] or not if (Arr[i] != Arr[j]) { // Checking 2nd condition i.e // whether Arr[Arr[i]] equal // to Arr[Arr[j]] or not. if (Arr[Arr[i] - 1] == Arr[Arr[j] - 1]) return true; } } } return false; } // Driver code static public void Main (){ int []Arr = { 3, 2, 1, 1, 4 }; int N = Arr.Length; if(checkIndices(Arr, N)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } // This code is Contributed by Sachin |
PHP
<?php// PHP implementation of the // above approach// Function that will tell whether// such Indices present or Not.function checkIndices($Arr, $N){ for ($i = 0; $i < $N - 1; $i++) { for ($j = $i + 1; $j < $N; $j++) { // Checking 1st condition i.e // whether Arr[i] equal to // Arr[j] or not if ($Arr[$i] != $Arr[$j]) { // Checking 2nd condition i.e // whether Arr[Arr[i]] equal to // Arr[Arr[j]] or not. if ($Arr[$Arr[$i] - 1] == $Arr[$Arr[$j] - 1]) return true; } } } return false;}// Driver Code$Arr = array(3, 2, 1, 1, 4);$N = sizeof($Arr);// Calling function.if(checkIndices($Arr, $N)) echo "Yes";else echo "No";// This code is contributed // by Akanksha Rai?> |
Javascript
<script>// Javascript implementation of the above approach// Function that will tell whether// such Indices present or Not.function checkIndices(Arr, N){ for (var i = 0; i < N - 1; i++) { for (var j = i + 1; j < N; j++) { // Checking 1st condition i.e whether // Arr[i] equal to Arr[j] or not if (Arr[i] != Arr[j]) { // Checking 2nd condition i.e whether // Arr[Arr[i]] equal to Arr[Arr[j]] or not. if (Arr[Arr[i] - 1] == Arr[Arr[j] - 1]) return true; } } } return false;}// Driver Codevar Arr = [ 3, 2, 1, 1, 4 ];var N = Arr.length;// Calling function.checkIndices(Arr, N) ? document.write( "Yes") : document.write( "No");</script> |
Output
Yes
Complexity Analysis:
- Time Complexity: O(N2)
- Auxiliary Space: O(1)
Optimization: The above approach used can be optimized to O(n) with the help of an unordered_map.
The steps used in this approach are as follows:
- First, we use an unordered_map to store the mapping of Arr[i] to i+1.
- Then, we iterate through the array and check if Arr[i] is already present in the hash table(unordered_map).
- If it is present, we check if the corresponding index in the hash table has the same value as Arr[i]. If yes then we have found the required indices and return ‘true’. If not, we continue the iteration.
- If we reach the end of the iteration and have not found the required indices, we return false.
Below is the code for the above approach.
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function that will tell whether// such Indices present or Not.bool checkIndices(int Arr[], int N){ // Hash table to store the mapping of Arr[i] to i+1 unordered_map<int, int> mp; for (int i = 0; i < N; i++) { // 1st condition is checked here i.e whether // Arr[i] equal to any other previous element // or not if (mp.find(Arr[i]) != mp.end()) { int j = mp[Arr[i]]; // Checking the second condition i.e whether // Arr[Arr[i]] equal to Arr[Arr[j-1]] or not. // Here we are taking j-1 as we are storing // the Arr[i] in i+1. if (Arr[j-1] == Arr[i]) { return true; } } mp[Arr[i]] = i+1; } return false;}// Driver Codeint main(){ int Arr[] = { 3, 2, 1, 1, 4 }; int N = sizeof(Arr) / sizeof(Arr[0]); // Calling function. checkIndices(Arr, N) ? cout << "Yes" : cout << "No"; return 0;}// This code is contributed by Pushpesh Raj. |
Python3
# Python 3 implementation of the above approach# Function that will tell whether# such Indices present or Not.def checkIndices(arr, n): # Dictionary to store the mapping of arr[i] to i+1 mp = {} for i in range(n): # 1st condition is checked here i.e whether # arr[i] equal to any other previous element # or not if arr[i] in mp: j = mp[arr[i]] # Checking the second condition i.e whether # arr[arr[i]] equal to arr[arr[j-1]] or not. # Here we are taking j-1 as we are storing # the arr[i] in i+1. if arr[j-1] == arr[i]: return True mp[arr[i]] = i+1 return False# Driver Codeif __name__ == "__main__": arr = [3, 2, 1, 1, 4] n = len(arr) # Calling function. print("Yes" if checkIndices(arr, n) else "No") |
Java
// Java implementation of the above approachimport java.io.*;class GFG { // Function that will tell whether // such Indices present or Not. static boolean checkIndices(int Arr[], int N) { // Hash table to store the mapping of Arr[i] to i+1 java.util.Map<Integer, Integer> mp = new java.util.HashMap<>(); for (int i = 0; i < N; i++) { // 1st condition is checked here i.e whether // Arr[i] equal to any other previous element // or not if (mp.containsKey(Arr[i])) { int j = mp.get(Arr[i]); // Checking the second condition i.e whether // Arr[Arr[i]] equal to Arr[Arr[j-1]] or // not. Here we are taking j-1 as we are // storing the Arr[i] in i+1. if (Arr[j - 1] == Arr[i]) { return true; } } mp.put(Arr[i], i + 1); } return false; } // Driver Code public static void main(String[] args) { int Arr[] = { 3, 2, 1, 1, 4 }; int N = Arr.length; // Calling function. if (checkIndices(Arr, N)) { System.out.println("Yes"); } else { System.out.println("No"); } }} |
C#
// C# implementation of the above approachusing System;using System.Collections.Generic;class Program { // Function that will tell whether // such Indices present or Not. static bool checkIndices(int[] Arr, int N) { // Hash table to store the mapping of Arr[i] to i+1 Dictionary<int, int> mp = new Dictionary<int, int>(); for (int i = 0; i < N; i++) { // 1st condition is checked here i.e whether // Arr[i] equal to any other previous element // or not if (mp.ContainsKey(Arr[i])) { int j = mp[Arr[i]]; // Checking the second condition i.e whether // Arr[Arr[i]] equal to Arr[Arr[j-1]] or // not. Here we are taking j-1 as we are // storing the Arr[i] in i+1. if (Arr[j - 1] == Arr[i]) { return true; } } mp[Arr[i]] = i + 1; } return false; } // Driver Code static void Main(string[] args) { int[] Arr = { 3, 2, 1, 1, 4 }; int N = Arr.Length; // Calling function. Console.WriteLine(checkIndices(Arr, N) ? "Yes" : "No"); }} |
Javascript
// Function that will tell whether such Indices present or Not.function checkIndices(arr) { // Dictionary to store the mapping of arr[i] to i+1 let mp = {}; for (let i = 0; i < arr.length; i++) { // 1st condition is checked here i.e whether arr[i] equal to any other previous element or not if (arr[i] in mp) { let j = mp[arr[i]]; // Checking the second condition i.e whether arr[arr[i]] equal to arr[arr[j-1]] or not. // Here we are taking j-1 as we are storing the arr[i] in i+1. if (arr[j-1] == arr[i]) { return true; } } mp[arr[i]] = i+1; } return false;}// Driver Codelet arr = [3, 2, 1, 1, 4];// Calling function.console.log(checkIndices(arr) ? "Yes" : "No"); |
Output
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
… [Trackback]
[…] Info to that Topic: geeksforgeeks.org/check-whether-i-j-exists-such-that-arr-i-arr-j-and-arr-arr-i-is-equal-to-arr-arr-j/ […]
… [Trackback]
[…] Info on that Topic: geeksforgeeks.org/check-whether-i-j-exists-such-that-arr-i-arr-j-and-arr-arr-i-is-equal-to-arr-arr-j/ […]