Teaching Kids Programming – Find the Maximum Achievable Number (Greedy Algorithm, Math)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given two integers, num and t. A number is achievable if it can become equal to num after applying the following operation: Increase or decrease the number by 1, and simultaneously increase or decrease num by 1. Return the maximum achievable number after applying the operation at most t times.

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 num by 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 num by 1.

Constraints:
1 <= num, t <= 50

Hints:
Let x be the answer, it is always optimal to decrease x in each operation and increase nums.

Find the Maximum Achievable Number

This is a simple math problem. We just have to greedily decrease x and increase the num in each iteration. The following solution is O(1) constant in both time and space.

1
2
3

class Solution:
    def theMaximumAchievableX(self, num: int, t: int) -> int:
        return num + t * 2

class Solution:
    def theMaximumAchievableX(self, num: int, t: int) -> int:
        return num + t * 2

–EOF (The Ultimate Computing & Technology Blog) —