Abstract / Summary

Given an array and a target, change one element to be as close to its half as possible and find the sum closest to the target.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 47% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a method that determines an integer value which, when used to cap all elements of a sorted array, yields a sum as close as possible to a given target. The algorithm first sorts the input, then checks whether the original sum already satisfies the target. If not, it iteratively computes a candidate average for the remaining unprocessed elements and decides whether this average can serve as the optimal cap. The method returns either the maximum element (when no reduction is needed) or the computed average that minimizes the deviation from the target.

Key Steps

Sorting and Initial Summation

arr.sort()
total = sum(arr)
size  = len(arr)

Sorting guarantees that elements are processed in non-decreasing order, which is essential for the subsequent logic that compares the running average with the current element. The total sum and the count of elements are stored for quick reference.

Early Exit When No Reduction Is Required

if total <= target:
    return arr[-1]

If the sum of the original array does not exceed the target, any capping operation would only increase the deviation. In this situation the method returns the largest element, effectively leaving the array unchanged.

Iterative Determination of the Capping Value

for a in arr:
    average = target // size
    modulo  = target %  size
    if modulo * 2 > size:
        average += 1

    if average <= a:
        return average

    target -= a
    size   -= 1

During each iteration the algorithm treats the yet-unprocessed portion of the array as a group whose elements could be uniformly reduced to a common value. The integer division target // size yields the floor of the ideal average, while the remainder target % size indicates how far the exact average lies from this floor. By checking whether the remainder is more than half of the divisor (modulo * 2 > size), the code decides whether rounding up yields a closer approximation, thereby implementing a manual rounding rule that avoids Python’s default rounding behavior.

If the computed average does not exceed the current element a, it means that capping all remaining elements at this average will not increase any of them beyond their original values. Consequently, the average is returned as the optimal cap.

When the average is larger than a, the current element is left unchanged, the target is reduced by a, and the size counter is decremented. This effectively removes the processed element from further consideration, allowing the algorithm to focus on the remaining suffix of the array.

Edge Cases Handled

The method gracefully handles the scenario where the original sum is already less than or equal to the target, returning the maximum element without entering the loop. It also correctly processes arrays containing duplicate values because the comparison average <= a works uniformly for equal elements. When the target is smaller than the smallest element, the first iteration will compute an average that is less than or equal to that element, causing an immediate return of the appropriate cap. The manual rounding logic ensures that cases where the exact average lies exactly halfway between two integers are resolved by rounding up, which aligns with the goal of minimizing absolute deviation.

Performance Optimizations

Sorting is performed once, and the subsequent loop processes each element at most once, eliminating the need for repeated scans. The use of integer division and a single multiplication (modulo * 2) to decide rounding avoids the overhead of floating-point arithmetic and built-in rounding functions. Updating target and size in place reduces the amount of auxiliary state, allowing the loop to operate with constant extra memory. By returning as soon as a suitable average is found, the algorithm often terminates early, especially when the optimal cap lies near the beginning of the sorted array. This early exit contributes to faster average-case performance.

Imagine a big box of numbered blocks. Some blocks have small numbers on them and some have very large numbers. The goal is to change all the big numbers so that when you add them all up, the total matches a special target number.

First, the pile of blocks is sorted from the smallest number to the largest. This makes it easy to see which blocks are little and which ones are huge.

The code then checks if the total of all the blocks is already smaller than the target. If the sum is already lower than what is needed, the best thing to do is keep the largest block exactly as it is because there is no reason to make anything smaller.

If the sum is too big, the code looks at each block one by one. It figures out what number would be fair to use for the remaining blocks so that they all add up to the target. Think of this like sharing cookies equally among friends.

The code calculates this fair share by dividing the current target by the number of blocks left to decide. It even knows how to round to the nearest whole number to be as accurate as possible.

If this fair share number is smaller than the current block, that fair share is the answer. If not, the code takes the current block away and moves on to the next one, making the pile of blocks to consider a little bit smaller and the target number a little bit lower until the perfect number is found.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python	Java			TS
	WalkCCC	C++		Python	Java
	leetcode.ca	C++		Python	Java	Go
	MemoryLimitExceeded	C++		Python
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	halfrost					Go
	JoshCrozier		JS
	lkwq007			Python
	lzl124631x	C++
	suxrobGM						C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
lzl124631x	C++
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality