aboutsummaryrefslogtreecommitdiff
path: root/max_element_decr_rearr.c
diff options
context:
space:
mode:
Diffstat (limited to 'max_element_decr_rearr.c')
-rw-r--r--max_element_decr_rearr.c39
1 files changed, 39 insertions, 0 deletions
diff --git a/max_element_decr_rearr.c b/max_element_decr_rearr.c
new file mode 100644
index 0000000..9c93905
--- /dev/null
+++ b/max_element_decr_rearr.c
@@ -0,0 +1,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
+}