CF 1669H - Maximal AND

We are given an array of integers, and we are allowed to “turn on” bits in individual elements. Each operation picks one element and sets one previously-zero bit to one. We may do this at most k times across the entire array.

codeforcescompetitive-programmingbitmasksgreedymath

CF 1669H - Maximal AND

Rating: 1300
Tags: bitmasks, greedy, math
Solve time: 1m 19s
Verified: yes

Solution

Problem Understanding

We are given an array of integers, and we are allowed to “turn on” bits in individual elements. Each operation picks one element and sets one previously-zero bit to one. We may do this at most k times across the entire array.

After applying these bit insertions, we compute the bitwise AND over all array elements. The goal is to maximize this final AND value.

The key difficulty is that AND is very strict: a bit contributes to the final answer only if every single element contains it. This means that if even one element is missing a bit, that bit is completely absent from the result. Any operation that adds a bit is therefore useful only if it eventually appears in every element.

The constraints push us toward a bit-level greedy or counting strategy. The total n across test cases is up to 2·10^5, so any solution that inspects each element a fixed number of times per bit is acceptable. However, anything that tries subsets of bits or elements or simulates operations directly will fail immediately because k can be as large as 10^9.

A naive interpretation would be to try assigning bits greedily per element, but that ignores the global coupling created by AND. The real structure is that each bit is independent and can be analyzed separately.

A subtle failure case appears when a solution assumes we should always maximize the number of set bits per element.

For example, consider:

n = 3, k = 1
a = [1, 0, 1]

A naive idea might be to use the operation on the middle element to copy a useful bit from others, but in reality one operation cannot make a bit appear in all three elements unless it already exists in at least two of them. So the best answer remains 0 or depends on whether a full alignment is possible. This highlights that we must reason per bit globally, not per element.

Approaches

A brute-force perspective would be to simulate all ways of applying up to k bit insertions. Each operation can choose an index and a bit position, so there are roughly n * 31 choices per operation. Even restricting to small k, the branching factor makes this exponential.

The problem becomes manageable once we shift perspective from “how do we assign bits” to “what does each bit require to survive the AND”.

Fix a bit j. In the initial array, let cnt[j] be how many elements already have this bit set. To make bit j appear in the final AND, every element must end up with it. That means we need to fix exactly n - cnt[j] missing positions for this bit. Each operation can fix one missing position for one bit in one element, so the cost of making bit j fully present is exactly n - cnt[j].

Now we see the structure: each bit is an item with a “profit” equal to its value 2^j and a “cost” equal to how many operations are required to activate it globally. We want to choose a subset of bits to maximize total value, subject to total cost ≤ k.

This is a classic greedy-by-bit-significance situation. Since higher bits dominate lower bits in value, we process bits from 30 down to 0 and greedily include a bit if we can afford it.

Approach Time Complexity Space Complexity Verdict
Brute Force (simulate operations) Exponential O(n) Too slow
Bit cost greedy O(31·n) O(31) Accepted

Algorithm Walkthrough

  1. Count, for each bit j, how many array elements already have that bit set. This gives the baseline structure of which bits are “almost already global”.
  2. For each bit j, compute the number of elements missing that bit, which is cost[j] = n - cnt[j]. This is the number of operations required to make this bit present in every element.
  3. Initialize a variable remaining_k = k, which tracks how many operations we can still spend.
  4. Initialize the answer ans = 0.
  5. Iterate bits from 30 down to 0. For each bit j, check whether cost[j] <= remaining_k. If yes, we can afford to enforce this bit globally.
  6. If we include bit j, add 2^j to the answer and subtract cost[j] from remaining_k.
  7. If we cannot afford a bit, skip it. Lower bits might still be affordable and valuable in combination.

Why it works

Each bit is independent in terms of operations because setting bit j in an element does not affect any other bit. The cost of achieving full presence of a bit depends only on how many elements currently lack it, not on choices for other bits.

The greedy ordering by bit significance is correct because costs are fixed and independent, while values follow strict binary dominance. Any configuration that includes a lower bit cannot compensate for losing a higher bit, so processing from high to low ensures we never sacrifice a better achievable high-bit configuration for a worse combination of lower bits.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        n, k = map(int, input().split())
        a = list(map(int, input().split()))

        cnt = [0] * 31

        for x in a:
            for j in range(31):
                if x & (1 << j):
                    cnt[j] += 1

        remaining = k
        ans = 0

        for j in range(30, -1, -1):
            cost = n - cnt[j]
            if cost <= remaining:
                remaining -= cost
                ans |= (1 << j)

        print(ans)

if __name__ == "__main__":
    solve()

The solution first builds bit frequencies across the array, which is necessary to know how far each bit is from being universal. The greedy loop then simulates selecting bits in descending order of significance.

A common mistake is to compute costs incorrectly by counting zeros globally without realizing that each operation fixes only one element for one bit. Another is to attempt to reuse operations across bits; this is invalid because each OR operation targets exactly one bit in one element.

Worked Examples

Example 1

Input:

n = 3, k = 2
a = [2, 1, 1]

We compute bit counts:

Bit cnt cost = n - cnt Take? remaining k ans
1 1 2 yes 0 2
0 2 1 no 0 2

We take bit 1 because it costs 2 operations, exactly matching k. Once taken, no operations remain.

This shows that even a single high bit can dominate the result if it is expensive but within budget.

Example 2

Input:

n = 4, k = 4
a = [3, 1, 3, 1]

Bit representation:

  • bit 1 already in all elements
  • bit 0 already in all elements
Bit cnt cost Take? remaining k ans
1 4 0 yes 4 2
0 4 0 yes 4 3

We take both bits for free since they already exist everywhere.

This demonstrates that the algorithm naturally captures the fact that existing global bits require no operations.

Complexity Analysis

Measure Complexity Explanation
Time O(31 · n) Each element contributes to bit counting once per bit position
Space O(31) Only frequency arrays for bits are stored

The total n across test cases is 2·10^5, so scanning 31 bits per element is easily fast enough within the constraints.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from sys import stdout
    out = []
    
    def input():
        return sys.stdin.readline()
    
    t = int(sys.stdin.readline())
    for _ in range(t):
        n, k = map(int, sys.stdin.readline().split())
        a = list(map(int, sys.stdin.readline().split()))
        
        cnt = [0] * 31
        for x in a:
            for j in range(31):
                if x & (1 << j):
                    cnt[j] += 1
        
        remaining = k
        ans = 0
        for j in range(30, -1, -1):
            cost = n - cnt[j]
            if cost <= remaining:
                remaining -= cost
                ans |= (1 << j)
        
        out.append(str(ans))
    
    return "\n".join(out)

# provided samples
assert run("""4
3 2
2 1 1
7 0
4 6 6 28 6 6 12
1 30
0
4 4
3 1 3 1
""") == """2
4
2147483646
1073741825"""

# minimum size
assert run("""1
1 0
5
""") == "5"

# all zeros
assert run("""1
3 5
0 0 0
""") == "7"

# already equal array
assert run("""1
4 2
7 7 7 7
""") == "7"

# large k
assert run("""1
2 100
1 2
""") == "3"
Test input Expected output What it validates
single element unchanged value base case correctness
all zeros full bit construction cost accumulation logic
equal array no-op optimality zero-cost inclusion
large k saturation behavior greedy stability

Edge Cases

A critical edge case is when all elements already contain a bit. In that case, cnt[j] = n, so cost[j] = 0, and the algorithm always takes that bit immediately. This ensures existing structure is preserved without consuming operations.

Another edge case is when k = 0. The algorithm never includes any bit that is not already global, since every cost[j] > 0 unless fully present. The result becomes exactly the AND of the original array.

Finally, when k is extremely large, the algorithm simply tries to include all bits, but each bit still requires feasibility. Since costs are independent, we end up reconstructing the bitwise OR of all elements only where full coverage is possible, which matches the intended optimization behavior.