Get Maximum in Generated Array

EASY

Description

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

Checkout 3 different approaches to solve Get Maximum in Generated Array. Click on different approaches to view the approach and algorithm in detail.

Naive Recursion

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

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 Analysis

Time Complexity: 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 Complexity: 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`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Get Maximum in Generated Array. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Get Maximum in Generated Array

Data Structures:

Array