From 20cefbfd4f00a9404bbf1e026f14a4dc3cc9ac16 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Tue, 10 Dec 2024 19:20:42 -0700 Subject: 2779. maximum beauty of an array after applying operation --- max_beauty_arr_apply_op.c | 32 ++++++++++++++++++++++++++++++++ max_beauty_arr_apply_op.py | 35 +++++++++++++++++++++++++++++++++++ 2 files changed, 67 insertions(+) create mode 100644 max_beauty_arr_apply_op.c create mode 100644 max_beauty_arr_apply_op.py diff --git a/max_beauty_arr_apply_op.c b/max_beauty_arr_apply_op.c new file mode 100644 index 0000000..b4097e0 --- /dev/null +++ b/max_beauty_arr_apply_op.c @@ -0,0 +1,32 @@ +// 2779. Maximum Beauty of an Array After Applying Operation +#include "leetcode.h" + +/* + * you are given a 0-indexed array 'nums' and a non-negative integer 'k'. in one + * operation you can do the following: choose an index 'i' that hasn't been + * chosen before from the range '[0, nums.len - 1]', replace 'nums[i]' with any + * integer from the range '[nums[i] - k, nums[i] + k]'. the beauty of the array + * is the length of the longest subsequence consisting of equal elements. return + * the maximum possible beauty of the array 'nums' after applying the operation + * any number of times. note that you can apply the operation to each index only + * once. a subsequence of an array is a new array generate from the original + * array by deleting some elements (possibly none) without changing the order of + * the remaining elements. + */ + +int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } + +int maximumBeauty(int *nums, int numsSize, int k) { + int i = 0, j; + qsort(nums, numsSize, sizeof(int), cmp); + for (j = 0; j < numsSize; j++) + if (nums[j] - nums[i] > k * 2) + i++; + return j - i; +} + +int main() { + int n1[] = {4, 6, 1, 2}, n2[] = {1, 1, 1, 1}; + printf("%d\n", maximumBeauty(n1, ARRAY_SIZE(n1), 2)); // expect: 3 + printf("%d\n", maximumBeauty(n2, ARRAY_SIZE(n2), 10)); // expect: 4 +} diff --git a/max_beauty_arr_apply_op.py b/max_beauty_arr_apply_op.py new file mode 100644 index 0000000..919ce4e --- /dev/null +++ b/max_beauty_arr_apply_op.py @@ -0,0 +1,35 @@ +# 2779. Maximum Beauty of an Array After Applying Operation + +""" +you are given a 0-indexed array 'nums' and a non-negative integer 'k'. in one +operation you can do the following: choose an index 'i' that hasn't been +chosen before from the range '[0, nums.len - 1]', replace 'nums[i]' with any +integer from the range '[nums[i] - k, nums[i] + k]'. the beauty of the array +is the length of the longest subsequence consisting of equal elements. return +the maximum possible beauty of the array 'nums' after applying the operation +any number of times. note that you can apply the operation to each index only +once. a subsequence of an array is a new array generate from the original +array by deleting some elements (possibly none) without changing the order of +the remaining elements. +""" + + +class Solution(object): + def maximumBeauty(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: int + """ + nums.sort() + i = 0 + for j in range(len(nums)): + if nums[j] - nums[i] > k * 2: + i += 1 + return j - i + 1 + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumBeauty(nums=[4, 6, 1, 2], k=2)) + print(obj.maximumBeauty(nums=[1, 1, 1, 1], k=10)) -- cgit v1.2.3