Values / Answer Space-இல் Binary Search

Search-on-answer போலவே; check-இல் prefix sums, greedy simulation வரும். "answer ≤ mid?" predicate-ஐ தெளிவாக எழுதுங்கள்.

Try this in Python

def max_k_with_prefix_constraint(nums: list[int], limit: int) -> int:
    """Toy: largest k such that sum of first k elements <= limit (monotone in k)."""
    p = [0]
    for x in nums:
        p.append(p[-1] + x)

    def ok(k: int) -> bool:
        return p[k] <= limit

    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if ok(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo


print(max_k_with_prefix_constraint([2, 2, 2, 2], 5))

Key takeaways

• Prefix sum range sum O(1).
• k maximize செய்ய upper-mid formula.
• எல்லை cases சோதி.