1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
// 1846. Maximum Element After Decreasing and Rearranging
#include "leetcode.h"
/*
* given an array of positive integers 'arr', perform some operations on 'arr'
* so that it satisfies these conditions:
* - the value of the first element in 'arr' must be 1
* - the absolute difference between any two adjacent elements must be less than
* or equal to 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 two types operations that you can perform any number of times:
* decrease the value of any element of 'arr' to a smaller positive integer
* rearrange the elements of 'arr' to be in any order
* return the maximum possible value of an element in 'arr' after performing the
* operations to satisfy the conditions.
*/
int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); }
int maximumElementAfterDecrementingAndRearranging(int *arr, int arr_size) {
qsort(arr, arr_size, sizeof(int), cmp);
int ans = 0, x = 1;
for (int i = 0; i < arr_size; i++)
if (arr[i] >= x) {
ans = (ans < x) ? x : ans;
x++;
}
return ans;
}
int main() {
int a1[] = {2, 2, 1, 2, 1}, a2[] = {100, 1, 1000}, a3[] = {1, 2, 3, 4, 5};
printf("%d\n", maximumElementAfterDecrementingAndRearranging(
a1, ARRAY_SIZE(a1))); // expect: 2
printf("%d\n", maximumElementAfterDecrementingAndRearranging(
a2, ARRAY_SIZE(a2))); // expect: 3
printf("%d\n", maximumElementAfterDecrementingAndRearranging(
a3, ARRAY_SIZE(a3))); // expect: 5
}
|