Given an array arr[] consisting of a permutation of numbers in the range [0, N – 1], the task is to find the length of the longest subset from the array such that the elements in the subset are of the form {arr[i], arr[arr[i]], arr[arr[arr[i]]], …}
Examples:
Input: arr[] = {5, 4, 0, 3, 1, 6, 2}
Output: 4
Explanation:
arr[arr[0]] is equal to arr[5]
arr[arr[arr[0]]] is equal to arr[6]
arr[arr[arr[arr[0]]]] is equal to arr[2]
One of the possible subsets from the array are {arr[0], arr[5], arr[6], arr[2]} = {5, 6, 2, 0}, which is the longest subset satisfying the given condition. Therefore, the required output is 4.Input: arr[] ={3, 1, 4, 0, 2}
Output: 2
Explanation:
arr[arr[0]] is equal to arr[3]
One of the possible subset from the array is {arr[0], arr[3]} = {3, 0}
Therefore, the required output is 2.
Approach: Follow the steps below to solve the problem:
- Initialize a variable res = 0 to store the length of the longest subset of the array that satisfying the condition.
- Traverse the array arr[] and perform the following operations:
- Check if arr[i] is equal to i or not. If found to be true, then update res = max(res, 1).
- Initialize a variable, say index = i, to store the index of elements of a subset from the given array.
- Iterate over elements of a subset while arr[index] != index, update the current element of the subset to the current index and also update index = arr[index].
- Finally, update the res to the maximum of res and the count of elements in the current subset.
- Finally, print the res.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find length of longest subset// such that subset { arr[i], arr[arr[i]], .. }int arrayNesting(vector<int> arr){ // Stores length of the longest subset // that satisfy the condition int res = 0; // Traverse in the array, arr[] for (int i = 0; i < arr.size(); i++) { // If arr[i] equals to i if (arr[i] == i) { // Update res res = max(res, 1); } else { // Count of elements in a subset int count = 0; // Stores index of elements in // the current subset int curr_index = i; // Calculate length of a subset that // satisfy the condition while (arr[curr_index] != curr_index) { int next_index = arr[curr_index]; // Make visited the current index arr[curr_index] = curr_index; // Update curr_index curr_index = next_index; // Update count count++; } // Update res res = max(res, count); } } return res;}// Driver Codeint main(){ vector<int> arr = { 5, 4, 0, 3, 1, 6, 2 }; int res = arrayNesting(arr); cout<<res;}// This code is contributed by mohit kumar 29. |
Java
// Java program to implement// the above approachimport java.io.*;import java.util.*;class sol { // Function to find length of longest subset // such that subset { arr[i], arr[arr[i]], .. } public int arrayNesting(int[] arr) { // Stores length of the longest subset // that satisfy the condition int res = 0; // Traverse in the array, arr[] for (int i = 0; i < arr.length; i++) { // If arr[i] equals to i if (arr[i] == i) { // Update res res = Math.max(res, 1); } else { // Count of elements in a subset int count = 0; // Stores index of elements in // the current subset int curr_index = i; // Calculate length of a subset that // satisfy the condition while (arr[curr_index] != curr_index) { int next_index = arr[curr_index]; // Make visited the current index arr[curr_index] = curr_index; // Update curr_index curr_index = next_index; // Update count count++; } // Update res res = Math.max(res, count); } } return res; }}// Driver Codeclass GFG { public static void main(String[] args) { sol st = new sol(); int[] arr = { 5, 4, 0, 3, 1, 6, 2 }; int res = st.arrayNesting(arr); System.out.println(res); }} |
C#
// C# program to implement// the above approachusing System;class sol { // Function to find length of longest subset // such that subset { arr[i], arr[arr[i]], .. } public int arrayNesting(int[] arr) { // Stores length of the longest subset // that satisfy the condition int res = 0; // Traverse in the array, arr[] for (int i = 0; i < arr.Length; i++) { // If arr[i] equals to i if (arr[i] == i) { // Update res res = Math.Max(res, 1); } else { // Count of elements in a subset int count = 0; // Stores index of elements in // the current subset int curr_index = i; // Calculate length of a subset that // satisfy the condition while (arr[curr_index] != curr_index) { int next_index = arr[curr_index]; // Make visited the current index arr[curr_index] = curr_index; // Update curr_index curr_index = next_index; // Update count count++; } // Update res res = Math.Max(res, count); } } return res; }}// Driver Codeclass GFG { static public void Main() { sol st = new sol(); int[] arr = { 5, 4, 0, 3, 1, 6, 2 }; int res = st.arrayNesting(arr); Console.WriteLine(res); }}// This code is contributed by Dharanendra L V |
Python3
# Python program for the above approach# Function to find length of longest subset# such that subset { arr[i], arr[arr[i]], .. }def arrayNesting(arr) : # Stores length of the longest subset # that satisfy the condition res = 0 # Traverse in the array, arr[] for i in range(len(arr)) : # If arr[i] equals to i if arr[i] == i : # Update res res = max(res, 1) else : # Count of elements in a subset count = 0 # Stores index of elements in # the current subset curr_index = i # Calculate length of a subset that # satisfy the condition while arr[curr_index] != curr_index : next_index = arr[curr_index] # Make visited the current index arr[curr_index] = curr_index # Update curr_index curr_index = next_index # Update count count += 1 # Update res res = max(res, count) return res# Driver Codeif __name__ == "__main__" : arr = [ 5, 4, 0, 3, 1, 6, 2 ] res = arrayNesting(arr) print(res) # This code is contributed by jana_sayantam.. |
Javascript
<script>// javascript program of the above approach // Function to find length of longest subset // such that subset { arr[i], arr[arr[i]], .. } function arrayNesting(arr) { // Stores length of the longest subset // that satisfy the condition let res = 0; // Traverse in the array, arr[] for (let i = 0; i < arr.length; i++) { // If arr[i] equals to i if (arr[i] == i) { // Update res res = Math.max(res, 1); } else { // Count of elements in a subset let count = 0; // Stores index of elements in // the current subset let curr_index = i; // Calculate length of a subset that // satisfy the condition while (arr[curr_index] != curr_index) { let next_index = arr[curr_index]; // Make visited the current index arr[curr_index] = curr_index; // Update curr_index curr_index = next_index; // Update count count++; } // Update res res = Math.max(res, count); } } return res; } // Driver Code let arr = [ 5, 4, 0, 3, 1, 6, 2 ]; let res = arrayNesting(arr); document.write(res);</script> |
Output:
4
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!
