1646. Get Maximum in Generated Array LeetCode Solution

In this guide, you will get 1646. Get Maximum in Generated Array LeetCode Solution with the best time and space complexity. The solution to Get Maximum in Generated Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Get Maximum in Generated Array solution in C++
4. Get Maximum in Generated Array solution in Java
5. Get Maximum in Generated Array solution in Python
6. Additional Resources

Problem Statement of Get Maximum in Generated Array

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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

1646. Get Maximum in Generated Array LeetCode Solution in C++

class Solution {
 public:
  int getMaximumGenerated(int n) {
    if (n == 0)
      return 0;
    if (n == 1)
      return 1;

    vector<int> nums(n + 1);
    nums[1] = 1;

    for (int i = 1; (2 * i + 1) <= n; ++i) {
      nums[2 * i] = nums[i];
      nums[2 * i + 1] = nums[i] + nums[i + 1];
    }

    return ranges::max(nums);
  }
};
/* code provided by PROGIEZ */

1646. Get Maximum in Generated Array LeetCode Solution in Java

class Solution {
  public int getMaximumGenerated(int n) {
    if (n == 0)
      return 0;
    if (n == 1)
      return 1;

    int[] nums = new int[n + 1];
    nums[1] = 1;

    for (int i = 1; (2 * i + 1) <= n; ++i) {
      nums[2 * i] = nums[i];
      nums[2 * i + 1] = nums[i] + nums[i + 1];
    }

    return Arrays.stream(nums).max().getAsInt();
  }
}
// code provided by PROGIEZ

1646. Get Maximum in Generated Array LeetCode Solution in Python

class Solution:
  def getMaximumGenerated(self, n: int) -> int:
    if n == 0:
      return 0
    if n == 1:
      return 1

    nums = [0] * (n + 1)
    nums[1] = 1

    i = 1
    while 2 * i + 1 <= n:
      nums[2 * i] = nums[i]
      nums[2 * i + 1] = nums[i] + nums[i + 1]
      i += 1

    return max(nums)
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.