You are given an array of positive integers arr. Perform some operations (possibly none) on arr so that it satisfies these conditions:
arr must be 1.1. In other words, abs(arr[i] - arr[i - 1]) <= 1 for each i where 1 <= i < arr.length (0-indexed). abs(x) is the absolute value of x.There are 2 types of operations that you can perform any number of times:
arr to a smaller positive integer.arr to be in any order.Return the maximum possible value of an element in arr after performing the operations to satisfy the conditions.
Example 1:
Input: arr = [2,2,1,2,1] Output: 2 Explanation: We can satisfy the conditions by rearrangingarrso it becomes[1,2,2,2,1]. The largest element inarris 2.
Example 2:
Input: arr = [100,1,1000] Output: 3 Explanation: One possible way to satisfy the conditions is by doing the following: 1. Rearrangearrso 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. Nowarr = [1,2,3], whichsatisfies the conditions. The largest element inarr 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.
Constraints:
1 <= arr.length <= 1051 <= arr[i] <= 109class Solution {
public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
Arrays.sort(arr);
arr[0] = 1;
int prev = 1, n = arr.length;
for (int i = 0; i < n; i++)
if (arr[i] - prev >= 1)
++prev;
return prev;
}
}