Maximize the Bitwise AND of Selected Elements with Increments

Quick Overview

Maximize the AND of selected array elements under an increment budget using descending-bit feasibility, minimal per-element costs, and cheapest-m selection.

Maximize the Bitwise AND of Selected Elements with Increments

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

Given a nonnegative integer array, choose exactly m elements. You may spend at most k operations, each increasing one array element by one. Return the greatest bitwise AND that can be achieved among the m chosen elements after the operations. ### Constraints & Assumptions Assume `1 <= m <= n`, k is a nonnegative integer, and values are nonnegative integers. This is the defined task identified by the source's numeric problem reference; the report supplies no additional interview-specific variant. For example, with values `[1,4,6]`, m=2, and k=2, increasing 4 to 6 gives two selected values equal to 6, so AND 6 is achievable. AND 7 would require increasing both selected values to at least 7, costing at least four operations, so the answer is 6. ### Clarifying Questions to Ask - Are increments the only allowed operation, and can unused operations remain? - Is m exactly the number of selected elements rather than a minimum? - What numeric range must the implementation support? ```hint Test a required bit mask For a proposed set of AND bits, calculate each element's cheapest increment-only destination containing all those bits, then choose the cheapest m elements. ``` ### What a Strong Answer Covers - A feasibility test using the m smallest independent increment costs. - The minimum value at least x that contains every required mask bit. - Greedily testing answer bits from most significant to least significant. - A justified highest bit and complexity accounting. ### Follow-up Questions - Why is simply replacing x by `x OR mask` sometimes unnecessarily expensive? - How would you recover the chosen elements and their final values?

Overview: Maximize the AND of selected array elements under an increment budget using descending-bit feasibility, minimal per-element costs, and cheapest-m selection.

Read the full Amazon Software Engineer interview experience this question came from

Amazon logo
Amazon
Nov 21, 2026
easySoftware EngineerTechnical ScreenCoding & Algorithms
0
0

Given a nonnegative integer array, choose exactly m elements. You may spend at most k operations, each increasing one array element by one. Return the greatest bitwise AND that can be achieved among the m chosen elements after the operations.

Constraints & Assumptions

Assume 1 <= m <= n, k is a nonnegative integer, and values are nonnegative integers. This is the defined task identified by the source's numeric problem reference; the report supplies no additional interview-specific variant.

For example, with values [1,4,6], m=2, and k=2, increasing 4 to 6 gives two selected values equal to 6, so AND 6 is achievable. AND 7 would require increasing both selected values to at least 7, costing at least four operations, so the answer is 6.

Clarifying Questions to Ask Guidance

  • Are increments the only allowed operation, and can unused operations remain?
  • Is m exactly the number of selected elements rather than a minimum?
  • What numeric range must the implementation support?

What a Strong Answer Covers Guidance

  • A feasibility test using the m smallest independent increment costs.
  • The minimum value at least x that contains every required mask bit.
  • Greedily testing answer bits from most significant to least significant.
  • A justified highest bit and complexity accounting.

Follow-up Questions Guidance

  • Why is simply replacing x by x OR mask sometimes unnecessarily expensive?
  • How would you recover the chosen elements and their final values?