diff options
author | Jack Sangdahl <[email protected]> | 2025-05-17 00:09:58 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-05-17 00:09:58 -0600 |
commit | 2304d32820d403740108de84125059c623686fc9 (patch) | |
tree | afcbfbc8235565f13c433091fd2e25996d11621d | |
parent | 9b6473451c15a328a71f11cdf69ff36379e4ef15 (diff) | |
download | leetcode-2304d32820d403740108de84125059c623686fc9.tar.gz leetcode-2304d32820d403740108de84125059c623686fc9.zip |
2897. apply operations on array to maximise sum of squares
-rw-r--r-- | apply_operations_arr_max_sqr.c | 37 | ||||
-rw-r--r-- | apply_operations_arr_max_sqr.py | 31 |
2 files changed, 68 insertions, 0 deletions
diff --git a/apply_operations_arr_max_sqr.c b/apply_operations_arr_max_sqr.c new file mode 100644 index 0000000..150c721 --- /dev/null +++ b/apply_operations_arr_max_sqr.c @@ -0,0 +1,37 @@ +// 2897. Apply Operations on Array to Maximize Sum of Squares +#include "leetcode.h" + +/* + * you are given a 0-indexed integer array 'nums' and a positive integer 'k'. + * you can do the following operation on the array any number of times: choose + * any two distinct indices 'i' and 'j' and simultaneously update the values of + * 'nums[i]' to '(nums[i] & nums[j])' and 'nums[j]' to '(nums[i] | nums[j])'. + * you have to choose 'k' elements from the final array and calcluate the sum of + * their squares. return the maximum sum of squares you can achieve. since the + * answer can be very large, return it modulo 10^9+7. + */ + +int maxSum(int *nums, int numsSize, int k) { + int cnt[32] = {0}; + for (int i = 0; i < numsSize; i++) + for (int j = 0; j < 32; j++) + if (nums[i] & (1 << j)) + cnt[j]++; + int ans = 0, mod = 1e9 + 7; + for (int i = 0; i < k; i++) { + int curr = 0; + for (int j = 0; j < 32; j++) + if (cnt[j] > 0) { + cnt[j]--; + curr += 1 << j; + } + ans = (ans + 1L * curr * curr % mod) % mod; + } + return ans; +} + +int main() { + int n1[] = {2, 6, 5, 8}, n2[] = {4, 5, 4, 7}; + printf("%d\n", maxSum(n1, ARRAY_SIZE(n1), 2)); // expect: 261 + printf("%d\n", maxSum(n2, ARRAY_SIZE(n2), 3)); // expect: 90 +} diff --git a/apply_operations_arr_max_sqr.py b/apply_operations_arr_max_sqr.py new file mode 100644 index 0000000..e3b5ade --- /dev/null +++ b/apply_operations_arr_max_sqr.py @@ -0,0 +1,31 @@ +# 2897. Apply Operations on Array to Maximize Sum of Squares +from collections import Counter + +""" +you are given a 0-indexed integer array 'nums' and a positive integer 'k'. +you can do the following operation on the array any number of times: choose +any two distinct indices 'i' and 'j' and simultaneously update the values of +'nums[i]' to '(nums[i] & nums[j])' and 'nums[j]' to '(nums[i] | nums[j])'. +you have to choose 'k' elements from the final array and calcluate the sum of +their squares. return the maximum sum of squares you can achieve. since the +answer can be very large, return it modulo 10^9+7. +""" + + +class Solution(object): + def maxSum(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: int + """ + cnt = Counter(i for j in nums for i in range(32) if j & (1 << i)) + return sum(sum((cnt[i] > j) << i for i in range(32)) ** 2 for j in range(k)) % ( + 10**9 + 7 + ) + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxSum(nums=[2, 6, 5, 8], k=2)) + print(obj.maxSum(nums=[4, 5, 4, 7], k=3)) |