Get Maximum in Generated Array
EasyPrompt
You are given an integer n. A 0-indexed integer array nums of length n + 1 is generated in the following way:
nums[0] = 0nums[1] = 1nums[2 * i] = nums[i]when2 <= 2 * i <= nnums[2 * i + 1] = nums[i] + nums[i + 1]when2 <= 2 * i + 1 <= n
Return the maximum integer in the array nums.
Example 1:
Input: n = 7
Output: 3
Explanation: According to the given rules:
nums[0] = 0
nums[1] = 1
nums[(1 * 2) = 2] = nums[1] = 1
nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
nums[(2 * 2) = 4] = nums[2] = 1
nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
nums[(3 * 2) = 6] = nums[3] = 2
nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
Hence, nums = [0,1,1,2,1,3,2,3], and the maximum is max(0,1,1,2,1,3,2,3) = 3.Example 2:
Input: n = 2
Output: 1
Explanation: According to the given rules, nums = [0,1,1]. The maximum is max(0,1,1) = 1.Example 3:
Input: n = 3
Output: 2
Explanation: According to the given rules, nums = [0,1,1,2]. The maximum is max(0,1,1,2) = 2.
Constraints:
0 <= n <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the generation rules into a recursive function. To find the maximum, it iterates through all indices from 0 to n and calls the recursive function for each, finding the maximum value. This method is conceptually simple but highly inefficient.
Algorithm
- The main function handles the base cases for
n < 2. - It initializes a variable
maxValto 0. - It then iterates from
i = 0ton. - In each iteration, it calls a recursive helper function
getValue(i)to compute the value ofnums[i]. - It updates
maxValwith the maximum value seen so far. - The
getValue(k)function is defined as follows:- Base case: If
kis 0, return 0. Ifkis 1, return 1. - Recursive step for even
k: returngetValue(k / 2). - Recursive step for odd
k: returngetValue(k / 2) + getValue(k / 2 + 1).
- Base case: If
Walkthrough
We define a function getValue(i) that computes nums[i] by strictly following the recurrence relation given in the problem. The base cases are getValue(0) = 0 and getValue(1) = 1. For any other index i, the function calls itself with smaller indices (i/2 or i/2 and i/2 + 1). The main function then iterates from 0 to n, calling getValue(i) for each i and tracking the maximum value seen. This approach is very inefficient because it recomputes the values for the same indices multiple times. For instance, calculating getValue(7) and getValue(6) both require getValue(3), which will be computed twice from scratch. This redundancy leads to an exponential number of calls.
class Solution { public int getMaximumGenerated(int n) { if (n < 2) { return n; } int maxVal = 0; for (int i = 0; i <= n; i++) { maxVal = Math.max(maxVal, getValue(i)); } return maxVal; } private int getValue(int k) { if (k == 0) { return 0; } if (k == 1) { return 1; } if (k % 2 == 0) { return getValue(k / 2); } else { return getValue(k / 2) + getValue(k / 2 + 1); } }}Complexity
Time
O(2^n). The number of recursive calls grows exponentially with `n`. This is because each call for an odd number `k` branches into two subproblems, and many subproblems (like `getValue(3)`) are re-calculated multiple times.
Space
O(log n). The space complexity is determined by the maximum depth of the recursion call stack. To compute `getValue(n)`, the recursion depth is proportional to `log n`.
Trade-offs
Pros
Simple to write as it's a direct translation of the problem's mathematical definition.
Cons
Extremely inefficient due to massive re-computation of values for the same indices.
Will result in a 'Time Limit Exceeded' error on most platforms for
ngreater than about 30-40.
This approach improves upon the naive recursion by using memoization to avoid recomputing results for the same subproblems. It's a form of top-down dynamic programming. An auxiliary array is used to store the results of nums[i] once they are computed, so subsequent calls for the same index can return the stored value in constant time.
Algorithm
- Handle base cases for
n < 2. - Create a memoization array
memoof sizen + 1and initialize it with a sentinel value (e.g., -1) to indicate that no value has been computed yet. - The main function iterates from
i = 0ton, calling a recursive helpergetValue(i, memo)and updating the maximum value found. - The
getValue(k, memo)function works as follows:- If
kis 0 or 1, returnk. - If
memo[k]is not the sentinel value, return it immediately. - Otherwise, compute the result based on whether
kis even or odd, using recursive calls. - Store the computed result in
memo[k]before returning it.
- If
Walkthrough
To fix the inefficiency of the naive recursive approach, we can store the results of getValue(i) in a memoization table (an array, memo). Before computing getValue(i), we first check if the result is already in our table. If it is, we return it directly. If not, we compute it recursively as before, but we store the result in memo[i] before returning. This ensures that the value for each index i from 0 to n is calculated exactly once. This technique is known as top-down dynamic programming.
class Solution { int[] memo; public int getMaximumGenerated(int n) { if (n < 2) { return n; } memo = new int[n + 1]; java.util.Arrays.fill(memo, -1); int maxVal = 0; // We need to find the max in the entire generated array, not just nums[n] for (int i = 0; i <= n; i++) { maxVal = Math.max(maxVal, getValue(i)); } return maxVal; } private int getValue(int k) { if (k == 0) { return 0; } if (k == 1) { return 1; } if (memo[k] != -1) { return memo[k]; } if (k % 2 == 0) { memo[k] = getValue(k / 2); } else { memo[k] = getValue(k / 2) + getValue(k / 2 + 1); } return memo[k]; }}Complexity
Time
O(n). Each value `nums[i]` for `i` from 0 to `n` is computed once. The main loop runs `n+1` times, and each call to `getValue` results in a constant number of operations (amortized) due to memoization.
Space
O(n). We need an array of size `n + 1` for the memoization table. The recursion stack depth contributes an additional O(log n), making the total space complexity O(n).
Trade-offs
Pros
Efficient, as it solves the overlapping subproblems issue.
Guarantees that each state
nums[i]is computed only once.Maintains a clear mapping from the recurrence relation.
Cons
Slightly more complex to implement than naive recursion due to the memoization table.
Has the overhead of recursive function calls, which can be marginally slower than a pure iterative solution.
This is the most efficient and straightforward approach, often called bottom-up dynamic programming. It simulates the generation process iteratively. We create an array to store the numbers and fill it from index 2 up to n, using the values that have already been computed. While filling the array, we keep track of the maximum value encountered.
Algorithm
- Handle the base cases: if
nis 0 or 1, returnn. - Create an integer array
numsof sizen + 1. - Initialize the first two values based on the rules:
nums[0] = 0andnums[1] = 1. - Initialize a variable
maxValto 1, as this is the maximum forn >= 1so far. - Iterate with an index
ifrom 2 ton. - Inside the loop, calculate
nums[i]based on previously computed values:- If
iis even,nums[i] = nums[i / 2]. - If
iis odd,nums[i] = nums[i / 2] + nums[i / 2 + 1].
- If
- After computing
nums[i], updatemaxVal = Math.max(maxVal, nums[i]). - After the loop finishes, return
maxVal.
Walkthrough
Instead of a top-down recursive approach, we can solve this problem iteratively from the bottom up. This avoids recursion overhead and is often more intuitive for simulation-style problems. We create an array nums of size n + 1. We know nums[0] and nums[1] from the problem description. We can then compute the rest of the values in order, from nums[2] up to nums[n]. When we compute nums[i], the values it depends on (nums[i/2] and nums[i/2 + 1]) have already been computed because their indices are smaller than i. We maintain a variable to track the maximum value as we generate the array.
class Solution { public int getMaximumGenerated(int n) { if (n <= 1) { return n; } int[] nums = new int[n + 1]; nums[0] = 0; nums[1] = 1; int maxVal = 1; for (int i = 2; i <= n; i++) { if (i % 2 == 0) { nums[i] = nums[i / 2]; } else { // For odd i, integer division i/2 is the same as (i-1)/2 nums[i] = nums[i / 2] + nums[i / 2 + 1]; } maxVal = Math.max(maxVal, nums[i]); } return maxVal; }}Complexity
Time
O(n). We iterate through the numbers from 2 to `n` once, and each calculation is a constant-time operation.
Space
O(n). An array of size `n + 1` is used to store the generated numbers.
Trade-offs
Pros
Most efficient in terms of performance as it avoids recursion overhead.
Easy to understand and implement.
Optimal time and space complexity for this problem.
Cons
Requires O(n) extra space for the array, which is unavoidable for this problem but worth noting.
Solutions
Solution
class Solution {public int getMaximumGenerated(int n) { if (n < 2) { return n; } int[] nums = new int[n + 1]; nums[1] = 1; for (int i = 2; i <= n; ++i) { nums[i] = i % 2 == 0 ? nums[i >> 1] : nums[i >> 1] + nums[(i >> 1) + 1]; } return Arrays.stream(nums).max().getAsInt(); }}class Solution {public: int getMaximumGenerated(int n) { if (n < 2) { return n; } int nums[n + 1]; nums[0] = 0; nums[1] = 1; for (int i = 2; i <= n; ++i) { nums[i] = i % 2 == 0 ? nums[i >> 1] : nums[i >> 1] + nums[(i >> 1) + 1]; } return *max_element(nums, nums + n + 1); }};class Solution: def getMaximumGenerated(self, n: int) -> int: if n < 2: return n nums = [0] * (n + 1) nums[1] = 1 for i in range(2, n + 1): nums[i] = nums[i >> 1] if i % 2 == 0 else nums[i >> 1] + nums[(i >> 1) + 1] return max(nums)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.