#1846
Maximum Element After Decreasing and Rearranging
specialist · 645 · lc medium +30 · verified · 65.8% accepted · 1,135 likes · top 71%
Description
You are given a positive integer array arr. Using any combination of these two operations:
- Decrease any element to any smaller positive integer.
- Rearrange the elements in any order.
The resulting array must have its first element equal to 1 and every consecutive pair differ by at most 1.
Return the maximum value any element can have after the operations.
Example 1:
Input: arr = [2,2,1,2,1]
Output: 2
Explanation:
We can satisfy the conditions by rearranging arr so it becomes [1,2,2,2,1].
The largest element in arr is 2.
Example 2:
Input: arr = [100,1,1000]
Output: 3
Explanation:
One possible way to satisfy the conditions is by doing the following:
1. Rearrange arr so it becomes [1,100,1000].
2. Decrease the value of the second element to 2.
3. Decrease the value of the third element to 3.
Now arr = [1,2,3], which satisfies the conditions.
The largest element in arr is 3.
Example 3:
Input: arr = [1,2,3,4,5]
Output: 5
Explanation: The array already satisfies the conditions, and the largest element is 5.
Code
1
2
3