4117. Minimum Range After Sum Operations
DifficultyMedium
Description
You are given three integers a, b, and c.
You may perform the following operation any number of times (including zero):
- Choose one of the three integers and replace it with the sum of the other two integers. The other two integers remain unchanged.
The range of three integers is defined as the difference between the maximum value and the minimum value.
Return the minimum range that can be obtained after performing the operation any number of times.
Example 1:
Input: a = 9, b = 2, c = 5
Output: 5
Explanation:
One sequence of operations which results in the minimum range is as follows:
- Set
atob + c = 2 + 5 = 7. The three integers are nowa = 7,b = 2,c = 5. - The range of the three integers is
max(7, 2, 5) - min(7, 2, 5) = 7 - 2 = 5.
Example 2:
Input: a = 5, b = 7, c = 6
Output: 2
Explanation:
Without doing any operations, the range of the three integers is max(5, 7, 6) - min(5, 7, 6) = 7 - 5 = 2.
Example 3:
Input: a = 3, b = 3, c = 3
Output: 0
Explanation:
Without doing any operations, the range of the three integers is max(3, 3, 3) - min(3, 3, 3) = 3 - 3 = 0.
Constraints:
1 <= a, b, c <= 100
Solutions
Solution 1: Sorting
Thinking
Each operation replaces one integer by the sum of the other two positive integers. The values can keep growing, so enumerating every sequence of operations has no natural stopping point.
The range is the maximum minus the minimum. A replacement is at least as large as either integer that stays, so the minimum never decreases. A smaller range then has to come from a smaller maximum.
After the three integers are sorted, the only replacement that can lower the maximum writes the sum of the other two in its place, and the resulting range is the middle value. Replacing the smallest or the middle value raises the maximum, and further operations after replacing the maximum cannot produce a smaller range. The answer is the smaller of the original range and that middle value.
Store \(a\), \(b\), and \(c\) in \(\textit{nums}\) and sort them, so \(\textit{nums}[0]\le\textit{nums}[1]\le\textit{nums}[2]\).
With no operation, the range is \(\textit{nums}[2]-\textit{nums}[0]\). All three integers are positive. An operation replaces the chosen integer by the sum of the other two, so the new integer is at least as large as either integer that remains, and the minimum never decreases. Once the minimum cannot decrease, the range can shrink only when the maximum is replaced by the sum of the other two. The triple becomes \(\textit{nums}[0]\), \(\textit{nums}[1]\), and \(\textit{nums}[0]+\textit{nums}[1]\), and the range equals \(\textit{nums}[1]\). If that sum is still at least the old maximum, the maximum does not fall. Another operation from there makes the new maximum at least \(\textit{nums}[0]+\textit{nums}[1]\), so the range is not smaller. Replacing the smallest or the middle integer by the sum of the other two produces a value greater than the old maximum, so that range is not smaller either.
The answer is therefore \(\min(\textit{nums}[2]-\textit{nums}[0], \textit{nums}[1])\).
The time complexity is \(O(1)\), and the space complexity is \(O(1)\).
1 2 3 4 5 | |
1 2 3 4 5 6 7 | |
1 2 3 4 5 6 7 8 | |
1 2 3 4 5 | |
1 2 3 4 | |