Maximize the Bitwise AND of K Elements After Spending an Increment Budget
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Online Assessment
You are given an array `arr` of non-negative integers, an integer `k` and a non-negative integer budget `c`.
First, you may increase elements of `arr`. Each increase adds a non-negative integer amount to one element, and the total added across all elements must not exceed `c`. You may spread the budget over several elements, put all of it on one element, or leave some of it unused. Elements can only be increased, never decreased.
Then you choose exactly `k` elements at distinct indices (they do not need to be contiguous) and take the bitwise AND of their values after the increases.
Return the largest bitwise AND you can obtain.
### Function Signature
```python
def max_and_after_increments(arr: list[int], k: int, c: int) -> int:
```
### Rules
- Every increase is a non-negative integer, and the sum of all increases is at most `c`.
- The `k` chosen elements must be at `k` different indices. Equal values at different indices may both be chosen.
- Increasing an element that is not chosen is allowed, but it simply wastes budget.
- With `k = 1`, the bitwise AND of a single element is that element's value.
- Return the maximum achievable AND value. It is unique even when several choices of increases and indices reach it.
### Constraints
- `1 <= len(arr) <= 10^5`
- `1 <= k <= len(arr)`
- `0 <= arr[i] <= 10^9`
- `0 <= c <= 10^9`
- No element can exceed `2 * 10^9` after the increases, so the answer fits in a 32-bit signed integer. Intermediate sums of increase amounts can exceed `2^31 - 1`, so use 64-bit integers in languages with fixed-width types.
### Examples
**Example 1**
```text
Input: arr = [5, 4, 1, 7, 2], k = 3, c = 3
Output: 6
```
Increase `4` by 2 and `5` by 1 (3 in total), then choose `6`, `6` and `7`: `6 & 6 & 7 = 6`. No allocation of at most 3 lets any three elements reach an AND of 7 or more.
**Example 2**
```text
Input: arr = [12, 10, 14, 7], k = 2, c = 0
Output: 12
```
With no budget, the best pair is `12` and `14`: `12 & 14 = 12`.
**Example 3**
```text
Input: arr = [1, 2], k = 2, c = 1
Output: 2
```
Adding 1 to the first element gives `[2, 2]` and `2 & 2 = 2`. Adding it to the second element gives `1 & 3 = 1`, and adding nothing gives `1 & 2 = 0`.
Overview: Given an array, a count k and a total budget of increments, raise elements so that the bitwise AND of some k chosen elements is as large as possible, and return that value. The problem tests bit manipulation, careful accounting of a shared budget, and an efficient solution for inputs of up to 100,000 elements.
Read the full Amazon Software Engineer interview experience this question came from
