1class Solution {
2    public int maximumAND(int[] nums, int k, int m) {
3        // Find the maximum value in the array to determine the bit range we need to examine.
4        int maxValue = 0;
5        for (int x : nums) {
6            maxValue = Math.max(maxValue, x);
7        }
8        // Account for the budget k, since increments could push values higher.
9        maxValue += k;
10
11        // Determine the number of relevant bits (highest set bit position + 1).
12        int maxBits = 32 - Integer.numberOfLeadingZeros(maxValue);
13        int n = nums.length;
14
15        // 'answer' is built greedily from the most significant bit downward.
16        int answer = 0;
17        // 'cost' holds the cost for each element to reach the candidate target value.
18        int[] cost = new int[n];
19
20        // Greedily try to set each bit from the highest position to the lowest.
21        for (int bit = maxBits - 1; bit >= 0; bit--) {
22            // Candidate target: the current answer with the current bit turned on.
23            int target = answer | (1 << bit);
24
25            for (int i = 0; i < n; i++) {
26                int x = nums[i];
27                // 'diff' contains the bits required by target that x does not yet have.
28                int diff = target & ~x;
29                // 'j' is the position just above the highest missing bit (0 if nothing missing).
30                int j = diff == 0 ? 0 : 32 - Integer.numberOfLeadingZeros(diff);
31                // Mask covering all bit positions below j.
32                int mask = (1 << j) - 1;
33                // Cost to raise x's lower bits up to target's lower bits.
34                cost[i] = (target & mask) - (x & mask);
35            }
36
37            // Sort costs ascending so we can pick the cheapest m elements.
38            Arrays.sort(cost);
39
40            // Sum the cost of the m cheapest elements.
41            long sum = 0;
42            for (int i = 0; i < m; i++) {
43                sum += cost[i];
44            }
45
46            // If we can afford this bit within budget k, keep it in the answer.
47            if (sum <= k) {
48                answer = target;
49            }
50        }
51
52        return answer;
53    }
54}
55

1class Solution {
2public:
3    int maximumAND(const vector<int>& nums, int k, int m) {
4        // Determine the highest possible value after adding k to the maximum element.
5        int max_val = ranges::max(nums) + k;
6
7        // Compute how many bits we need to consider.
8        // __builtin_clz counts leading zeros; (32 - clz) gives the bit-length.
9        int bit_count = max_val > 0 ? 32 - __builtin_clz(max_val) : 0;
10
11        int ans = 0;                       // Greedily built answer (target value so far).
12        vector<int> cost(nums.size());     // Cost for each element to reach the candidate target.
13
14        // Greedily try to set bits from the most significant to the least significant.
15        for (int bit = bit_count - 1; bit >= 0; bit--) {
16            // Candidate target: current answer with the current bit turned on.
17            int target = ans | (1 << bit);
18
19            // Compute the cost to upgrade each number so that it covers all set bits of target.
20            for (size_t i = 0; i < nums.size(); i++) {
21                int x = nums[i];
22
23                // Bits required by target that x currently lacks.
24                int diff = target & ~x;
25
26                // Highest bit position that must be fixed (0 if none).
27                int high_bit = diff == 0 ? 0 : 32 - __builtin_clz(diff);
28
29                // Mask covering all bit positions up to (and including) the highest needed bit.
30                long long mask = (1LL << high_bit) - 1;
31
32                // Minimum increment to make x's lower bits match target's lower bits.
33                // (target & mask) is the desired lower-bit pattern; (x & mask) is the current one.
34                cost[i] = (target & mask) - (x & mask);
35            }
36
37            // Pick the m cheapest numbers to satisfy the target.
38            ranges::sort(cost);
39            long long sum = accumulate(cost.begin(), cost.begin() + m, 0LL);
40
41            // If the m smallest costs fit within budget k, lock in this bit.
42            if (sum <= k) {
43                ans = target;
44            }
45        }
46
47        return ans;
48    }
49};
50

1/**
2 * Maximizes the AND value of m chosen numbers after spending at most k on increments.
3 * Uses a greedy bit-by-bit strategy from the most significant bit downward.
4 *
5 * @param nums - The input array of numbers.
6 * @param k - The total budget available for increments.
7 * @param m - The number of elements that must satisfy the target pattern.
8 * @returns The maximum achievable AND value.
9 */
10function maximumAND(nums: number[], k: number, m: number): number {
11    // Determine the highest bit position we need to consider.
12    // The maximum possible value after increments is max(nums) + k,
13    // so the number of significant bits is 32 - leading zeros of that value.
14    const maxBit: number = 32 - Math.clz32(Math.max(...nums) + k);
15
16    let answer: number = 0;
17    const n: number = nums.length;
18
19    // Reusable array storing the incremental cost for each element
20    // to conform to the candidate target pattern.
21    const cost: number[] = new Array(n);
22
23    // Greedily attempt to set each bit, from the most significant to the least.
24    for (let bit = maxBit - 1; bit >= 0; bit--) {
25        // Candidate target: the bits we've already locked in, plus the current bit.
26        const target: number = answer | (1 << bit);
27
28        // Compute the cost to bring each number up to the candidate target.
29        for (let i = 0; i < n; i++) {
30            const x: number = nums[i];
31
32            // Bits that the target requires but x does not currently have.
33            const diff: number = target & ~x;
34
35            // Highest set bit position in diff; this defines the relevant range
36            // of low-order bits we must account for when raising x to target.
37            const highestDiffBit: number = diff === 0 ? 0 : 32 - Math.clz32(diff);
38
39            // Mask covering all bits below highestDiffBit.
40            const mask: number = (1 << highestDiffBit) - 1;
41
42            // Incremental cost: align x's low bits to match target's low bits.
43            cost[i] = (target & mask) - (x & mask);
44        }
45
46        // Sort costs ascending so we can pick the m cheapest elements.
47        cost.sort((a, b) => a - b);
48
49        // Sum the cost of the m cheapest conversions.
50        let sum: number = 0;
51        for (let i = 0; i < m; i++) {
52            sum += cost[i];
53        }
54
55        // If we can afford it within budget k, lock in this bit.
56        if (sum <= k) {
57            answer = target;
58        }
59    }
60
61    return answer;
62}
63