1646. Get Maximum in Generated Array
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 53.2%
Problem Breakdown
The problem requires generating an array nums of length n + 1 based on specific rules and then finding the maximum value in that array. The rules for generating the array are:
nums[0] = 0nums[1] = 1- For even indices:
nums[2 * i] = nums[i] - For odd indices:
nums[2 * i + 1] = nums[i] + nums[i + 1]
The input is a single integer n, and the output is the maximum value in the generated array. The constraints are that 0 <= n <= 100.
Implicit constraints include:
- If
nis 0, the array will only contain one element[0]. - If
nis 1, the array will be[0, 1].
Intuition
A brute-force approach would involve generating the array and then iterating through it to find the maximum value. However, this approach is inefficient because it requires two passes over the array (one for generation and one for finding the maximum).
The key insight is that we can generate the array in a single pass while keeping track of the maximum value encountered so far. This reduces the time complexity from O(2n) to O(n).
Approach
- Initialize an empty list
numswith sizen + 1. - Set the base cases:
nums[0] = 0andnums[1] = 1. - Iterate through the array starting from index 2 up to
n:- If the index is even, set
nums[i] = nums[i // 2]. - If the index is odd, set
nums[i] = nums[i // 2] + nums[i // 2 + 1].
- If the index is even, set
- Keep track of the maximum value encountered during the array generation.
- Return the maximum value.
Complexity Analysis
- Time Complexity: O(n) because we iterate through the array once to generate it and find the maximum value.
- Space Complexity: O(n) for storing the generated array.
Solution
def getMaximumGenerated(n: int) -> int:
if n == 0:
return 0
nums = [0] * (n + 1)
nums[1] = 1
max_value = 1
for i in range(2, n + 1):
if i % 2 == 0:
nums[i] = nums[i // 2]
else:
nums[i] = nums[i // 2] + nums[i // 2 + 1]
max_value = max(max_value, nums[i])
return max_value
Edge Cases Handled
- n = 0: The array is
[0], and the maximum value is0. - n = 1: The array is
[0, 1], and the maximum value is1. - n = 2: The array is
[0, 1, 1], and the maximum value is1. - n = 3: The array is
[0, 1, 1, 2], and the maximum value is2. - n = 7: The array is
[0, 1, 1, 2, 1, 3, 2, 3], and the maximum value is3.
This solution efficiently generates the array and finds the maximum value in a single pass, adhering to the constraints and handling all edge cases.