Bishu and Soldiers
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}]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] }; });}