Problem solving this array based problem?

general
, ,
1

given an array Sets S[K] for 0 ≤ K < N are defined as follows:
S[K] = { A[K], A[A[K]], A[A[A[K]]], … }.
find the size of the largest set S[K] for this array. The function should return 0 if the array is empty.
for [5,4,0,3,1,6,2] ans is 4.

2

I need more details on the question. Whats the time complexity? The constraints? Is it necessary to have an efficient algo or even a brute force will do?

I think the algo steps are simple in ‘naïve approach’

  1. Run a Loop from 0 to n-1, with arr[I] begin the element under inspection
  2. now that we have chosen arr[I], we increment answer by 1. Now in another loop (preferable while loop), we check if arr[I] is more than n-1. If its not, then we increment answer by 1 and I = arr[I], else we stop checking and note the value of answer.
  3. Once the while loop ends (i.e. we get a value more than n-1 i.e. out of index) we note it (value of variable ans, which is nothing but how many times did the while loop run) and compare it with maximum value achieved till now. If ans>max, then max = ans.
  4. We set answer to 0 again and iterate similarly through all elements.

This algo will pass ~60-80% of test cases.

WATCH OUT! CORNER CASES

  1. The first corner case is like array = {1,0,3,4}. Here, if we start from index 0, it sends us to 1st index, and if we goto 1st index, it sends us BACK TO 0TH index. This results in infinite loop. We must maintain a check of what indexes we visited. For this, I would make a bool array and set it to true at start of loop. After visiting the index, would change its value to false and use if and break statements to terminate the while loop in case it sends us back to a visited element. Eg, in above, we would set bool[0]=false , then goto index 1. We set bool[1] = false, do the stuff, and when it sends us back to index 0, we find bool[0] is false and hence the while loop stops.

I cant comment more on corner cases due to lack of constraints, but yeah, this is what I feel the naïve solution is. I suspect dp is involved in this Q in some way or the other, but I am no expert in dp so I wont comment.

Get back to me with constraints, like number of queries per test case, range of valued, time limit, any TLE problem etc.

3

@vijju123 is right, you have to provide the full question or link with relevant constraint and right explanation.

4

provide full question or link .