Apply Operations on Array to Maximize Sum of Squares Solution
Apply Operations on Array to Maximize Sum of Squares solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Apply Operations on Array to Maximize Sum of Squares is a hard coding problem on arrays, hash table and greedy, asked in Amazon, Google and Sprinklr interviews.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Greedy, Bit Manipulation
- Asked at: Amazon, Google, Sprinklr
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of positive integers and a positive integer k. Any number of times, you may pick two distinct indices i and j and simultaneously replace nums[i] with nums[i] AND nums[j] and nums[j] with nums[i] OR nums[j].
Afterwards you choose k elements of the final array. Return the maximum possible sum of their squares, modulo 10^9 + 7.
Example 1
Input: nums = [1,2,4], k = 1
Output: 49
Explanation: Merging everything into one element gives 7, and 7² = 49.
Example 2
Input: nums = [3,3], k = 2
Output: 18
Example 3
Input: nums = [5,2,8,1], k = 2
Output: 226
Explanation: Bit 0 appears twice, the others once, so the best two values are 15 and 1: 225 + 1.
Constraints
1 <= k <= nums.length <= 10^51 <= nums[i] <= 10^9
Hints for Apply Operations on Array to Maximize Sum of Squares
Hint 1
Look at one bit position across the whole array. Does the operation change how many elements have that bit set?
Hint 2
It does not: AND and OR just move a bit from one element to the other. And by repeating the operation, every bit can be pushed onto any element that wants it.
Hint 3
So only the per-bit counts matter. Squares reward concentration: build the largest possible number from one copy of every available bit, then the next largest from what remains,
ktimes.
How to solve Apply Operations on Array to Maximize Sum of Squares
The operation preserves, for every bit, how many elements carry it, and it can move bits freely. So the reachable arrays are exactly those with the same per-bit counts, and squares are maximised by stacking bits onto as few elements as possible.
Approach
- Count
cnt[b], the number of elements with bitbset, forbfrom 0 to 29. - Repeat
ktimes: buildxby taking bitbfor everybwithcnt[b] > 0(and decrement that count); addx²to the answer modulo10^9 + 7. - Return the sum.
Why it works
Applying the operation to p and q yields p AND q and p OR q: a bit set in both stays in both, a bit set in one moves to the OR side, so each bit's count is unchanged, and repeating it gathers all shared bits onto one element. For a fixed total, moving a bit of value v from a smaller number s to a larger l changes the sum of squares by (l+v)² + (s-v)² - l² - s² = 2v(l - s + v) > 0, so the greedy stacking — each new number takes one copy of every remaining bit — is optimal, and the largest k numbers are the first k built.
Complexity
- Time —
O(30 · (n + k)) - Space —
O(30)
Pitfalls
- The built numbers stay below 2^30 but their squares reach 2^60 — reduce and multiply in 64 bits (or split the multiplication).
- Take the modulus only when adding squares; the choice of numbers is made on true values.
- Once the counts run out, the remaining chosen elements are 0 and add nothing.
Reference solution
Python
from typing import List
def maxSum(nums: List[int], k: int) -> int:
cnt = [0] * 30
for v in nums:
for b in range(30):
cnt[b] += (v >> b) & 1
total = 0
for _ in range(k):
x = 0
for b in range(30):
if cnt[b] > 0:
cnt[b] -= 1
x |= 1 << b
total = (total + x * x) % 1000000007
return totalJava
public static int maxSum(int[] nums, int k) {
final long M = 1000000007L;
int[] cnt = new int[30];
for (int v : nums) {
for (int b = 0; b < 30; b++) cnt[b] += (v >> b) & 1;
}
long total = 0;
for (int t = 0; t < k; t++) {
long x = 0;
for (int b = 0; b < 30; b++) {
if (cnt[b] > 0) { cnt[b]--; x |= 1L << b; }
}
total = (total + x * x % M) % M;
}
return (int) total;
}C++
int maxSum(vector<int>& nums, int k) {
const long long M = 1000000007LL;
int cnt[30] = {0};
for (int v : nums) {
for (int b = 0; b < 30; b++) cnt[b] += (v >> b) & 1;
}
long long total = 0;
for (int t = 0; t < k; t++) {
long long x = 0;
for (int b = 0; b < 30; b++) {
if (cnt[b] > 0) { cnt[b]--; x |= 1LL << b; }
}
total = (total + x * x % M) % M;
}
return (int) total;
}JavaScript
var maxSum = function(nums, k) {
var M = 1000000007, cnt = new Array(30).fill(0);
for (var i = 0; i < nums.length; i++) {
for (var b = 0; b < 30; b++) cnt[b] += (nums[i] >> b) & 1;
}
var total = 0;
for (var t = 0; t < k; t++) {
var x = 0;
for (var c = 0; c < 30; c++) {
if (cnt[c] > 0) { cnt[c]--; x |= 1 << c; }
}
var r = x % M;
total = (total + ((r * (r >>> 16)) % M * 65536 + r * (r & 65535)) % M) % M;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets