We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Get Maximum in Generated Array

Difficulty: Easy

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

Key Insights

  • The array is built using a recursive relationship based on the index.
  • The even indexed values are derived directly from previous indices.
  • The odd indexed values are the sum of two previous indices, leading to potential peaks in values.
  • The maximum value will always be found among the generated values, which can be directly computed without storing the entire array.

Space and Time Complexity

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

Solution

The solution involves generating the array based on the defined rules. We can utilize an array to store values as we compute them. For each index from 2 to n, we apply the rules to populate the array. Finally, we return the maximum value found in the array.

Code Solutions

def getMaximumGenerated(n):
    if n == 0:
        return 0
    if n == 1:
        return 1

    nums = [0] * (n + 1)  # Initialize the array
    nums[0] = 0
    nums[1] = 1

    max_value = 1  # Start with the known maximum

    for i in range(1, (n // 2) + 1):
        if 2 * i <= n:
            nums[2 * i] = nums[i]  # Fill even index
            max_value = max(max_value, nums[2 * i])
        if 2 * i + 1 <= n:
            nums[2 * i + 1] = nums[i] + nums[i + 1]  # Fill odd index
            max_value = max(max_value, nums[2 * i + 1])

    return max_value
← Back to All Questions