Get Maximum in Generated Array

Easy
1106.

Get Maximum in Generated Array

Get Maximum in Generated Array is an easy coding problem on arrays and simulation, asked in Amazon and Google interviews.

Build an array nums of length n + 1 by these rules:

  • nums[0] = 0
  • nums[1] = 1 (when n >= 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 largest value in nums.

Example 1

Input
n = 7
Output
3
Explanation
nums = [0,1,1,2,1,3,2,3], whose maximum is 3.

Example 2

Input
n = 2
Output
1
Explanation
nums = [0,1,1].

Example 3

Input
n = 0
Output
0

Constraints

  • 0 <= n <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var getMaximumGenerated = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Get Maximum in Generated Array — Problem & Solution

Get Maximum in Generated Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Get Maximum in Generated Array is an easy coding problem on arrays and simulation, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays, Simulation
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Build an array nums of length n + 1 by these rules:

  • nums[0] = 0
  • nums[1] = 1 (when n >= 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 largest value in nums.

Example 1

Input: n = 7
Output: 3
Explanation: nums = [0,1,1,2,1,3,2,3], whose maximum is 3.

Example 2

Input: n = 2
Output: 1
Explanation: nums = [0,1,1].

Example 3

Input: n = 0
Output: 0

Constraints

  • 0 <= n <= 100

Hints for Get Maximum in Generated Array

  1. Hint 1

    Every entry depends only on entries with smaller indices.

  2. Hint 2

    Fill the array from index 2 upwards, using i / 2 (and i / 2 + 1 for odd i).

  3. Hint 3

    Track the maximum as you go, and handle n = 0 before touching nums[1].

How to solve Get Maximum in Generated Array

The recurrence only looks backwards — nums[i] uses indices around i / 2 — so filling the array left to right computes every value once.

Approach

  1. If n == 0 return 0.
  2. Set nums[0] = 0, nums[1] = 1, best = 1.
  3. For i from 2 to n: let h = i / 2; set nums[i] = nums[h] for even i, otherwise nums[h] + nums[h + 1]; update best.
  4. Return best.

Why it works

For i >= 2, both h and h + 1 are smaller than i, so the values they need are already final when nums[i] is computed. Every entry is therefore exactly what the rules define, and the running maximum covers all of them.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • For n = 0 the array is just [0]; writing nums[1] would go out of bounds.
  • An odd index 2i + 1 uses nums[i] + nums[i + 1], with i = (index - 1) / 2.
  • The maximum is not always at the last index — n = 7 peaks at index 5.

Reference solution

Python

def getMaximumGenerated(n: int) -> int:
    if n == 0:
        return 0
    nums = [0] * (n + 1)
    nums[1] = 1
    for i in range(2, n + 1):
        h = i // 2
        nums[i] = nums[h] if i % 2 == 0 else nums[h] + nums[h + 1]
    return max(nums)

Java

public static int getMaximumGenerated(int n) {
    if (n == 0) return 0;
    int[] nums = new int[n + 1];
    nums[1] = 1;
    int best = 1;
    for (int i = 2; i <= n; i++) {
        int h = i / 2;
        nums[i] = i % 2 == 0 ? nums[h] : nums[h] + nums[h + 1];
        best = Math.max(best, nums[i]);
    }
    return best;
}

C++

int getMaximumGenerated(int n) {
    if (n == 0) return 0;
    vector<int> nums(n + 1, 0);
    nums[1] = 1;
    int best = 1;
    for (int i = 2; i <= n; i++) {
        int h = i / 2;
        nums[i] = i % 2 == 0 ? nums[h] : nums[h] + nums[h + 1];
        best = max(best, nums[i]);
    }
    return best;
}

JavaScript

var getMaximumGenerated = function(n) {
    if (n === 0) return 0;
    var nums = [0, 1], best = 1;
    for (var i = 2; i <= n; i++) {
        var h = Math.floor(i / 2);
        nums.push(i % 2 === 0 ? nums[h] : nums[h] + nums[h + 1]);
        if (nums[i] > best) best = nums[i];
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays