Scale Engineer

Get Maximum in Generated Array

Easy
#1511Time: 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`.
Data structures
Array

Prompt

You are given an integer n. A 0-indexed integer array nums of length n + 1 is generated in the following way:

  • nums[0] = 0
  • nums[1] = 1
  • nums[2 * i] = nums[i] when 2 <= 2 * i <= n
  • nums[2 * i + 1] = nums[i] + nums[i + 1] when 2 <= 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 maxVal to 0.
  • It then iterates from i = 0 to n.
  • In each iteration, it calls a recursive helper function getValue(i) to compute the value of nums[i].
  • It updates maxVal with the maximum value seen so far.
  • The getValue(k) function is defined as follows:
    • Base case: If k is 0, return 0. If k is 1, return 1.
    • Recursive step for even k: return getValue(k / 2).
    • Recursive step for odd k: return getValue(k / 2) + getValue(k / 2 + 1).

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 n greater than about 30-40.

Solutions

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();  }}

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