I had an amazon SDE 1 OA which followed the 1 DSA question + 1 AI-Assisted Coding Repo Question. The coding repo questions was very easy, however the DSA one was unattemptable for me. Partly due to me never doing a bit manipulation sum in my life

Question:

You are given an array of integers capacities, an integer deployment_size, and an integer budget.

You may increase any capacity by any non-negative integer amount, as long as the total amount added across all capacities does not exceed budget.

Choose exactly deployment_size capacities after applying these increases.

Return the maximum possible bitwise AND of the chosen capacities.

Funnily enough, I used a brute-force recursive approach to enumerate all possible pairs which obviously TLE'd for a majority of the test cases.

Just wanted to know what the actual approach for solving such a problem is. Im assuming there is some greedy bit construction involved, but don't really have much domain knowledge to even get started.