Unique Array

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:

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[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)

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