Apply Operations on Array to Maximize Sum of Squares

Apply Operations on Array to Maximize Sum of Squares - Problem

You are given a 0-indexed integer array nums and a positive integer k.

You can perform the following operation on the array any number of times:

Choose any two distinct indices i and j
Simultaneously update nums[i] to (nums[i] AND nums[j]) and nums[j] to (nums[i] OR nums[j])

Here, OR denotes the bitwise OR operation, and AND denotes the bitwise AND operation.

After performing operations, you must choose k elements from the final array and calculate 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⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,6,4], k = 2

› Output: 85

💡 Note: After operations, we can achieve [6,7] by optimally distributing bits. Sum = 6² + 7² = 36 + 49 = 85.

Example 2 — Single Element

$ Input: nums = [4], k = 1

› Output: 16

💡 Note: Only one element, no operations possible. Sum = 4² = 16.

Example 3 — Larger Array

$ Input: nums = [1,2,3,4,5], k = 3

› Output: 245

💡 Note: Optimal distribution concentrates bits to maximize the 3 largest values, achieving maximum sum of squares.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹
1 ≤ k ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Given array [2,6,4] and k=2, analyze bit patterns

Bit Operations

Use AND/OR operations to redistribute bits optimally

Maximize Output

Select k=2 largest values and calculate sum of squares

Key Takeaway

🎯 Key Insight: AND/OR operations preserve bit totals - the optimal strategy concentrates bits to maximize squares

Asked in

G Google 25 M Microsoft 20 A Amazon 15

The key insight is that AND/OR operations preserve the total number of bits at each position. The optimal strategy is to greedily distribute bits from most significant to least significant positions to maximize the k largest values. Best approach uses bit frequency counting with greedy assignment. Time: O(n log max_val + k log k), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Bit Frequency Greedy	O(n log max_val + k log k)	O(log max_val)	Count bit frequencies and distribute optimally to maximize squares
Brute Force with All Operations	O(2^(n²) × n log n)	O(n)	Try all possible AND/OR operations and track maximum sum
Greedy with Priority Queue	O(n log max_val + k log k × log max_val)	O(k + log max_val)	Use heap to efficiently track and maximize the k largest values

Bit Frequency Greedy — Algorithm Steps

Count frequency of each bit position across all numbers
Greedily distribute bits to create k largest numbers
Calculate sum of squares modulo 10^9+7

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Bits

Count 1s at each bit position

Distribute

Assign bits greedily from MSB to LSB

Calculate

Sum of squares of k largest values

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int solution(int *nums, int n, int k) {
    // Count frequency of each bit position
    int bitCount[32] = {0};
    for (int i = 0; i < n; i++) {
        for (int bit = 0; bit < 32; bit++) {
            if (nums[i] & (1 << bit)) {
                bitCount[bit]++;
            }
        }
    }
    
    // Greedily assign bits to create k largest numbers
    int *result = calloc(k, sizeof(int));
    
    // For each bit position from most significant to least
    for (int bit = 31; bit >= 0; bit--) {
        int count = bitCount[bit];
        // Sort to assign bits to smallest current values
        qsort(result, k, sizeof(int), compare);
        for (int i = 0; i < count && i < k; i++) {
            result[i] |= (1 << bit);
        }
    }
    
    // Calculate sum of squares
    long long total = 0;
    for (int i = 0; i < k; i++) {
        total = (total + (long long)result[i] * result[i]) % MOD;
    }
    
    free(result);
    return (int)total;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    int nums[100], n = 0;
    char *token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log max_val + k log k)

Count bits for each number plus sorting k results

⚡ Linearithmic

Space Complexity

O(log max_val)

Array to store bit frequencies (up to 32 bits for integers)

✓ Linear Space

32.9K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bit Frequency Greedy — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler