Apply Operations on Array to Maximize Sum of Squares

Hard
1335.

Apply Operations on Array to Maximize Sum of Squares

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.

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^5
  • 1 <= nums[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxSum = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • 1 <= nums[i] <= 10^9

Hints for Apply Operations on Array to Maximize Sum of Squares

  1. Hint 1

    Look at one bit position across the whole array. Does the operation change how many elements have that bit set?

  2. 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.

  3. 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, k times.

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

  1. Count cnt[b], the number of elements with bit b set, for b from 0 to 29.
  2. Repeat k times: build x by taking bit b for every b with cnt[b] > 0 (and decrement that count); add x² to the answer modulo 10^9 + 7.
  3. 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 total

Java

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