  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Unique Array

Last Updated on December 13, 2022 by Prepbytes Hashing

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 = 3, A = 5, A = 0, A = 1, A = 6, A = 2, A = 4.

For various values of i :

for i = 0, we have -> (A, A, A, A, A) = (3, 1, 5, 2, 0)

for i = 1, we have -> (A, A, A, A, A) = (5, 2, 0, 3, 1)

for i = 2, we have -> (A, A, A, A, A) = (0, 3, 1, 5, 2)

for i = 3, we have -> (A, A, A, A, A) = (1, 5, 2, 0, 3)

for i = 4, we have -> (A, A)                   = (6, 4)

for i = 5, we have -> (A, A, A, A, A) = (2, 0, 3, 1, 5)

for i = 6, we have -> (A, A)                   = (4, 6)

For indexes = 0, 1, 2, 3, and 5, Maximum length of unique array A is 5.``````

### SOLVING APPROACH:

1. The idea is to use an additional `Visited Array` for storing if an element was previously visited or not.

2. 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.

3. Keep updating the `maximum` value with the `maximum count` value.

### SOLUTIONS:

```
#include

int 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

```
```
#include
using 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 = {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.