Katkat
Back

Maximize protected population and bitwise AND

AmazonSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to optimize resource allocation using greedy approaches with priority queues and bitwise bit-manipulation techniques to satisfy mathematical constraints.

Part 1: Maximizing Protected Population

You are given an array population of size n, where each element represents the number of people in a region. You have k mobile relief units. Each unit can be moved from its current index i to any index j within a range d (i.e., |i - j| <= d). Each region can host at most one relief unit. Return the maximum total population that can be covered by the k relief units. Note that each unit covers the population of the region it is placed in.

Constraints

  • 1 <= n <= 10^5
  • 1 <= k <= n
  • 0 <= d <= n
  • 0 <= population[i] <= 10^9

Part 2: Bitwise AND Maximization

You are given an array of integers nums and an integer m. You can perform an increment operation on any element in nums at most m times in total (each operation increases one element by 1). Your goal is to maximize the bitwise AND of all elements in the final array.

Constraints

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 10^6
  • 0 <= m <= 10^9

Examples

Example 1 (Part 1): Input: population = [10, 2, 5, 20], k = 2, d = 1 Output: 30 Explanation: Place units at index 0 (pop 10) and index 3 (pop 20). Total = 30.

Example 2 (Part 2): Input: nums = [10, 11], m = 1 Output: 10 Explanation: Increasing 10 by 1 makes the array [11, 11], bitwise AND is 11. Wait, if m=1, we can increase 10 to 11. The AND is 11.

Hints

Hint 1

For Part 1, treat this as a matching problem where units have constrained mobility, which can be solved greedily using a priority queue to select the largest available population within reachable indices.

Hint 2

For Part 2, iterate through bits from most significant to least significant to determine if it is possible to set that bit in the final AND result by calculating the total increment cost required.

Hint 3

In Part 2, to check if bit `b` can be set, verify if the cost to round up all numbers to the nearest value having bit `b` set (and keeping higher determined bits) is within `m`.

Follow-up questions

  • How does the time complexity change in Part 1 if `d` is very large compared to `n`?
  • Can you optimize the bitwise AND check in Part 2 from O(n * log(max_val)) to something faster using prefix sums or precomputation?
  • What edge cases arise in Part 2 when `m` is large enough to overflow the current range of numbers?