Bishu and Soldiers

Medium

Problem

Bishu has power P. He defeats every soldier whose power is at most P. Given the soldiers' powers and several queries of P, report for each query how many soldiers he defeats and the sum of their powers.

Example 1

Input:  powers = [1, 2, 3, 4, 5, 6, 7], queries = [3, 10, 2]
Output: (3, 6), (7, 28), (2, 3)

Also asked as: Bishu and Soldiers

Test cases

Case 1

Input:    [1,2,3,4,5,6,7], [3,10,2]
Expected: [{"killed":3,"powerGained":6},{"killed":7,"powerGained":28},{"killed":2,"powerGained":3}]

Case 2

Input:    [5,5], [4,5]
Expected: [{"killed":0,"powerGained":0},{"killed":2,"powerGained":10}]

Case 3

Input:    [3,1,2], [2]
Expected: [{"killed":2,"powerGained":3}]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Sort + prefix sums + binary search per query

Time O(n log n + q log n)Space O(n)

Sort soldier powers, precompute prefix sums. For each round power P, binary-search the count of soldiers with power ≤ P and read the matching prefix sum.

function bishu(powers, queries) {
powers.sort((a, b) => a - b);
const prefix = [0];
for (const p of powers) prefix.push(prefix[prefix.length - 1] + p);
return queries.map((P) => {
let lo = 0, hi = powers.length;
while (lo < hi) { const mid = (lo + hi) >> 1; powers[mid] <= P ? (lo = mid + 1) : (hi = mid); }
return { killed: lo, powerGained: prefix[lo] };
});
}