Skip to main content

Uber

Uber OA-8 2023

Problem Description

You are starting a Debate Club in your college and want to make its opening as eye-catching as possible! To achieve this, you plan to host a mock round table conference among the students. You sent out invitations to your colleagues, but they have one condition: each colleague has a friend and will only attend the event if they can sit next to that friend. The friend cannot be the same person.

You are given a 0-indexed integer array friends, where friends[i] denotes the friend of the ith colleague. Your task is to return the maximum number of colleagues that can be invited to the meeting.

Input Format

  • An array of integers friends where friends[i] denotes the friend of the ith colleague.

Output Format

  • An integer: The maximum number of colleagues that can be invited to the meeting.

Constraints

  • N == friends.length
  • 2<=N<=10^4
  • 0<=friends[i]<=N - 1
  • friends[i] != i
  • The execution time limit is 0.5 seconds (C++).
  • The memory limit is 1 GB.

Sample Test Case

Input

friends = [3, 0, 1, 4, 1]

Output

4

Explanation

Colleague 2 cannot be invited because the two spots next to their friend 1 are already taken. Therefore, the maximum number of employees that can be invited to the meeting is 4.