Tap here to switch tabs
Problem
Submissions

Problem: Maximum Element After Decreasing and Rearranging

Maximum Element After Decreasing and Rearranging asks you to reorder and decrease a positive integer array so it starts at one, adjacent values differ by at most one, and its largest value is maximized.

Statement

You are given an array of positive integers arr. You can perform two types of operations any number of times:

  1. Decrease the value of any element in arr to any smaller positive integer.

  2. Rearrange the elements of arr in any order.

Return the maximum possible value of an element in arr after applying the operations such that arr satisfies the following conditions:

  1. The first element of arr must be equal to 11.

  2. The absolute difference between any two adjacent elements must be at most 11. That is, ∣|arr[i]−[i] - arr[i−1]∣≤1[i - 1]| \leq 1 for all 1≤i<1 \leq i < arr.length (using 00 based indexing).

Constraints:

  • 1≤1 \leq arr.length ≤105\leq 10^5

  • 1≤1 \leq arr[i] ≤109\leq 10^9

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Maximum Element After Decreasing and Rearranging

Maximum Element After Decreasing and Rearranging asks you to reorder and decrease a positive integer array so it starts at one, adjacent values differ by at most one, and its largest value is maximized.

Statement

You are given an array of positive integers arr. You can perform two types of operations any number of times:

  1. Decrease the value of any element in arr to any smaller positive integer.

  2. Rearrange the elements of arr in any order.

Return the maximum possible value of an element in arr after applying the operations such that arr satisfies the following conditions:

  1. The first element of arr must be equal to 11.

  2. The absolute difference between any two adjacent elements must be at most 11. That is, ∣|arr[i]−[i] - arr[i−1]∣≤1[i - 1]| \leq 1 for all 1≤i<1 \leq i < arr.length (using 00 based indexing).

Constraints:

  • 1≤1 \leq arr.length ≤105\leq 10^5

  • 1≤1 \leq arr[i] ≤109\leq 10^9