Last Updated on December 13, 2022 by Prepbytes

### CONCEPTS USED:

Hashing

### DIFFICULTY LEVEL:

Easy

### PROBLEM STATEMENT`(`

SIMPLIFIED`)`

:

Given an array

`A`

with`N`

elements containing all elements from`0`

to`N-1`

, your task is to find the`maximum`

length of an`Unique Array`

.

** Unique Array**:

It contains elements in this manner,

`(A[i], A[A[i]], A[A[A[i]]], ...)`

for any value of `i`

and the elements are

`unique`

.Suppose the first element in

`A`

starts with the selection of element`A[i]`

of`index = i`

then next element in`A`

will be`A[A[i]]`

, and then`A[A[A[i]]]`

, till you don’t find a duplicate element in the unique array`A`

.

**See original problem statement here**

#### For Example:

```
Input : N = 7, A = [3, 5, 0, 1, 6, 2, 4]
Output: 5
Explanation : We have,
A[0] = 3, A[1] = 5, A[2] = 0, A[3] = 1, A[4] = 6, A[5] = 2, A[6] = 4.
For various values of i :
for i = 0, we have -> (A[0], A[3], A[1], A[5], A[2]) = (3, 1, 5, 2, 0)
for i = 1, we have -> (A[1], A[5], A[2], A[0], A[3]) = (5, 2, 0, 3, 1)
for i = 2, we have -> (A[2], A[0], A[3], A[1], A[5]) = (0, 3, 1, 5, 2)
for i = 3, we have -> (A[3], A[1], A[5], A[2], A[0]) = (1, 5, 2, 0, 3)
for i = 4, we have -> (A[4], A[6]) = (6, 4)
for i = 5, we have -> (A[5], A[2], A[0], A[3], A[1]) = (2, 0, 3, 1, 5)
for i = 6, we have -> (A[6], A[4]) = (4, 6)
For indexes = 0, 1, 2, 3, and 5, Maximum length of unique array A is 5.
```

### SOLVING APPROACH:

The idea is to use an additional

`Visited Array`

for storing if an element was previously visited or not.Traverse the array and for each element run a while loop and check if it was previously visited or not, if

`Not`

, mark it as visited, increment the value of`count`

and consider this element as our next index and keep repeating the same process till an element is found which was previously visited.Keep updating the

`maximum`

value with the`maximum count`

value.

### SOLUTIONS:

#includeint max(int a, int b){ return (a>b)? a:b; } int main() { int t; scanf("%d", &t); while(t--){ int n; scanf("%d", &n); int arr[n]; for(int i=0; i

#includeusing namespace std; int main() { int t; cin>>t; while(t--){ int n; cin>>n; int arr[n]; for(int i=0; i >arr[i]; /* creating a hash array for marking if the element was marked previously or not */ int visited[1000000] = {0}; int ans = 0; /* start from every index and find for max value */ for(int i=0; i

import java.util.*; import java.io.*; import java.lang.Math; public class Main { public static void main(String args[]) throws IOException { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t != 0){ int n = sc.nextInt(); int arr[] = new int[n]; for(int i=0; i

for _ in range(int(input())): n = int(input()) arr = list(map(int,input().split())) visited = [0 for i in range(1000000)] ans = 0 for i in range(n): count = 0 curr = arr[i] while visited[curr] == 0: visited[curr] = 1 count += 1 curr = arr[curr] ans = max(ans, count) print(ans)

**Space Complexity**:

`O(N)`

, due to additional `Visited Array`

.
[forminator_quiz id="543"]

This article tried to discuss the concept of Hashing. Hope this blog helps you understand and solve the problem. To practice more problems on Hashing you can check out MYCODE | Competitive Programming.