Problem Brief

Server Selection

FULLTIMEOA

See Amazon online assessment and hiring insights

Amazon Web Services (AWS) provides highly scalable solutions for applications hosted on their servers. A company using AWS is planning to scale up horizontally and wants to buy servers from a list of available options.

Find the maximum number of servers (as a subsequence from the list) that can be rearranged so that the absolute difference between adjacent servers (including circular adjacency) is ≤ 1.

Conditions:

A circular sequence is formed → So first and last servers are also considered adjacent.
A subsequence means elements can be removed but the order is preserved.

Formal: Given an array powers[] of n integers:

Find the maximum subsequence length such that it can be rearranged into a circular array where abs(a[i] - a[i+1]) ≤ 1 for all i, and abs(a[m-1] - a[0]) ≤ 1 where m is the length of the subsequence.

1Example 1

Input

powers = [4, 3, 5, 1, 2, 1]

Output

Explanation

Valid Candidates:

[1, 2, 2, 1] → valid circular arrangement
[3, 1, 2, 2] → can be rearranged to [1, 2, 3, 2] which is valid

Invalid:

[3, 1, 2] → no rearrangement makes circular adjacent difference ≤ 1

ans should be 4..