We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Apply Operations on Array to Maximize Sum of Squares

Number: 3153

Difficulty: Hard

Paid? No

Companies: Sprinklr

Problem Description

You are given a 0-indexed integer array nums and a positive integer k. You may perform the following operation any number of times: choose two distinct indices i and j and simultaneously update nums[i] to (nums[i] AND nums[j]) and nums[j] to (nums[i] OR nums[j]) (using bitwise AND/OR). After performing operations, you must choose exactly k elements from the final array and return the maximum possible sum of their squares modulo 10^9+7.

Key Insights

  • The allowed operation does not change, for each bit position, the total number of ones across the array.
  • For every bit b, if you let cnt[b] be the number of numbers that originally have the bth bit set, then cnt[b] remains invariant.
  • Because each element is an integer constructed from bits, you can “transfer” bits between numbers. However, note that a given number can have at most one copy of a particular bit.
  • To maximize the sum of squares when choosing k numbers, it is best to “concentrate” as many bits as possible into the same numbers (since (a+b)^2 > a^2 + b^2).
  • For each bit b, if cnt[b] ≥ k then every selected number can receive that bit. Otherwise (cnt[b] < k), you have cnt[b] copies that must be placed into cnt[b] distinct numbers.
  • An optimal final configuration for the k numbers is to let every number start with a “base” value (from all bits having at least k ones) and then, for the remaining bits (with cnt[b] < k), assign the bit to as many numbers as possible in a concentrated way. In fact, one optimal assignment is to set the i-th largest bucket’s extra sum as the sum of 2^b for every bit b for which cnt[b] ≥ i+1.
  • The final answer is the sum over all k buckets of (base + extra_i)^2 modulo 10^9+7.

Space and Time Complexity

Time Complexity: O(n + k · B) where B is the number of bits (B ≤ 32)
Space Complexity: O(k) for storing the extra contributions per bucket

Solution

We start by counting for each bit position (from 0 to 31) the number of numbers in nums that have that bit set. For each bit:

  1. If cnt[b] ≥ k, we add 2^b to a variable called base. This means every chosen number will always have that bit.
  2. If cnt[b] < k (and at least one number has that bit), then we know there are cnt[b] extra copies that we must assign to cnt[b] distinct numbers. To maximize the sum of squares, we concentrate as many different bits as possible in the same bucket. An optimal assignment can be derived by “stacking” the extra bits: let extra[0] be increased by 2^b if cnt[b] ≥ 1, extra[1] increased if cnt[b] ≥ 2, and so on.
  3. Finally, for 0 ≤ i < k, the i-th chosen number is taken as base + extra[i]. The answer is then the sum of squares of these k numbers computed modulo 10^9+7.

The key “gotcha” is that although we can rearrange bits arbitrarily while obeying the constraint that a given bit may appear at most once in each number, if a bit appears fewer than k times overall it must be distributed among different numbers. This forces an optimal assignment where the i-th bucket receives contributions from those bits that occur at least i+1 times.

We now provide complete code solutions in multiple languages.

Code Solutions

# Python solution with detailed comments

MOD = 10**9 + 7

def maximizeSumSquares(nums, k):
    # Count how many numbers have each bit set (assume 32-bit integers)
    bitCount = [0] * 32
    for num in nums:
        for b in range(32):
            if num & (1 << b):
                bitCount[b] += 1

    base = 0
    # extras[i] will store additional value that the i-th chosen number can get from bits available less than k copies
    extras = [0] * k

    # For each bit position
    for b in range(32):
        bitValue = 1 << b
        if bitCount[b] >= k:
            # If count is at least k, every chosen number can have this bit
            base = (base + bitValue) % MOD  # mod taken later in square sum; but addition mod not necessary here
        elif bitCount[b] > 0:
            # There are bitCount[b] copies available from this bit,
            # they must go to distinct numbers.
            # In an optimal assignment, assign them to the buckets with the greatest extra values.
            # Here we follow the observation:
            # For each bit, the extra contribution goes to the first bitCount[b] numbers.
            r = bitCount[b]
            for i in range(r):
                extras[i] += bitValue

    # Now, form the final k chosen numbers: each is base plus its extra contribution.
    ans = 0
    for extra in extras:
        value = base + extra
        # Compute square modulo MOD
        ans = (ans + (value % MOD) * (value % MOD)) % MOD

    return ans

# Example usage:
# nums = [2,6,5,8], k = 2
# print(maximizeSumSquares([2,6,5,8], 2)) # Expected output: 261
← Back to All Questions