2769. Find the Maximum Achievable Number
SourceWeekly Contest 353 Q1DifficultyEasyRating1191
Description
Given two integers, num and t. A number x is achievable if it can become equal to num after applying the following operation at most t times:
- Increase or decrease
xby1, and simultaneously increase or decreasenumby1.
Return the maximum possible value of x.
Example 1:
Input: num = 4, t = 1
Output: 6
Explanation:
Apply the following operation once to make the maximum achievable number equal to num:
- Decrease the maximum achievable number by 1, and increase
numby 1.
Example 2:
Input: num = 3, t = 2
Output: 7
Explanation:
Apply the following operation twice to make the maximum achievable number equal to num:
- Decrease the maximum achievable number by 1, and increase
numby 1.
Constraints:
1 <= num, t <= 50
Solutions
Solution 1: Mathematics
Thinking
Each operation moves \(x\) and \(\textit{num}\) one step in opposite directions, at most \(t\) times; we want the largest \(x\) that can meet \(\textit{num}\). Stepping them toward each other is unnecessary.
One operation shrinks \(x-\textit{num}\) by \(2\), so the largest feasible \(x\) is \(\textit{num}+2t\).
Notice that every time we can decrease \(x\) by \(1\) and increase \(\textit{num}\) by \(1\), the difference between \(x\) and \(\textit{num}\) will decrease by \(2\), and we can do this operation at most \(t\) times, so the maximum reachable number is \(\textit{num} + t \times 2\).
The time complexity is \(O(1)\), and the space complexity is \(O(1)\).
1 2 3 | |
1 2 3 4 5 | |
1 2 3 4 5 6 | |
1 2 3 | |
1 2 3 | |