aboutsummaryrefslogtreecommitdiff
path: root/apply_operations_arr_max_sqr.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-05-17 00:09:58 -0600
committerJack Sangdahl <[email protected]>2025-05-17 00:09:58 -0600
commit2304d32820d403740108de84125059c623686fc9 (patch)
treeafcbfbc8235565f13c433091fd2e25996d11621d /apply_operations_arr_max_sqr.c
parent9b6473451c15a328a71f11cdf69ff36379e4ef15 (diff)
downloadleetcode-2304d32820d403740108de84125059c623686fc9.tar.gz
leetcode-2304d32820d403740108de84125059c623686fc9.zip
2897. apply operations on array to maximise sum of squares
Diffstat (limited to 'apply_operations_arr_max_sqr.c')
-rw-r--r--apply_operations_arr_max_sqr.c37
1 files changed, 37 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
+}