Maximize protected population with one-step guard shifts

Q: Maximize protected population with one-step guard shifts

This question evaluates the ability to reason about constrained local moves and optimize a numerical objective over an array, testing skills in array manipulation, combinatorial optimization, and interpretation of binary state representations.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

There are n cities in a line (1-indexed). You are given:

population[1..n] : population of each city
unit : a binary string of length n , where unit[i] = '1' means city i initially has a security guard, and unit[i] = '0' means it does not.

A guard may be moved at most once. A move consists of shifting a guard from city i to city i-1 (one step left), only if:

i > 1 , and
city i-1 currently has no guard.

You may perform moves in any order.

After all moves, the “protected population” is the sum of populations of the cities that end up with a guard.

Compute the maximum protected population achievable.

Example:

population = [10, 5, 8, 9, 6]
unit = "01101"

Maximize protected population with one-step guard shifts

Quick Overview

Comments (0)