Scale Engineer

Find the Maximum Achievable Number

Easy
#2486Time: O(4^t) The `isAchievable` function has a branching factor of 4 and a maximum depth of `t`. This leads to an exponential number of calls, making the complexity `O(4^t)`. The outer loop for `x` is negligible in comparison.Space: O(t) The space complexity is determined by the maximum depth of the recursion stack, which is `t`.
Patterns
Math

Prompt

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 x by 1, and simultaneously increase or decrease num by 1.

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 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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves checking every possible number x starting from a high value and decreasing. For each x, we simulate the process to see if it can be made equal to num within t operations. The simulation is done using a recursive function that explores all possible outcomes.

Algorithm

  • The main idea is to search for the maximum achievable number x by starting from a high value and iterating downwards.
  • For each candidate x, we check if it's possible to make x and num equal in at most t steps.
  • This check is performed by a recursive function, isAchievable(currentX, currentNum, stepsLeft), which simulates the process.
  • isAchievable function logic:
    • Base Case 1: If currentX == currentNum, they are equal, so we return true.
    • Base Case 2: If stepsLeft == 0 and they are not equal, we've run out of operations, so we return false.
    • Recursive Step: The function explores all four possible operations by making a recursive call for each:
      1. isAchievable(currentX + 1, currentNum + 1, stepsLeft - 1)
      2. isAchievable(currentX + 1, currentNum - 1, stepsLeft - 1)
      3. isAchievable(currentX - 1, currentNum + 1, stepsLeft - 1)
      4. isAchievable(currentX - 1, currentNum - 1, stepsLeft - 1)
    • If any of these recursive calls return true, it means a path to equality exists, and the function returns true. Otherwise, it returns false.
  • The first value of x (iterating downwards) for which isAchievable returns true is the maximum possible value.

Walkthrough

We want to find the maximum achievable x. A simple strategy is to start checking from a large number and go downwards. The first number we find that is "achievable" will be our answer.

A safe upper bound to start from can be derived from the constraints. Since num <= 50 and t <= 50, num + 2*t is at most 50 + 100 = 150. We can start our search from a number like 200.

The core of this approach is the isAchievable(current_x, current_num, steps_left) function. This function checks if current_x and current_num can be made equal using steps_left operations.

class Solution {    public int theMaximumAchievableX(int num, int t) {        // Start checking from a reasonably high number downwards.        // num + 2*t is the actual answer, so starting there is efficient.        // For a true brute-force, we might start from a hardcoded limit like 200.        for (int x = num + 2 * t; x >= 1; x--) {            if (isAchievable(x, num, t)) {                return x;            }        }        return -1; // Should not be reached    }     private boolean isAchievable(long currentX, long currentNum, int stepsLeft) {        if (currentX == currentNum) {            return true;        }        if (stepsLeft == 0) {            return false;        }         // Explore all 4 possible operations        if (isAchievable(currentX + 1, currentNum + 1, stepsLeft - 1)) return true;        if (isAchievable(currentX + 1, currentNum - 1, stepsLeft - 1)) return true;        if (isAchievable(currentX - 1, currentNum + 1, stepsLeft - 1)) return true;        if (isAchievable(currentX - 1, currentNum - 1, stepsLeft - 1)) return true;         return false;    }}

Complexity

Time

O(4^t) The `isAchievable` function has a branching factor of 4 and a maximum depth of `t`. This leads to an exponential number of calls, making the complexity `O(4^t)`. The outer loop for `x` is negligible in comparison.

Space

O(t) The space complexity is determined by the maximum depth of the recursion stack, which is `t`.

Trade-offs

Pros

  • Simple to conceptualize as it directly models the problem statement.

Cons

  • Extremely inefficient due to its exponential time complexity.

  • Will result in a 'Time Limit Exceeded' error for the given constraints.

Solutions

class Solution {public  int theMaximumAchievableX(int num, int t) { return num + t * 2; }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem