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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Get Maximum in Generated Array

Number: 1769

Difficulty: Easy

Paid? No

Companies: Amazon

Problem Description

Given an integer n, generate a 0-indexed array nums of length n + 1 using the following rules:

  1. nums[0] = 0
  2. nums[1] = 1
  3. For each integer i such that 2 * i <= n, set nums[2 * i] = nums[i].
  4. For each integer i such that 2 * i + 1 <= n, set nums[2 * i + 1] = nums[i] + nums[i + 1]. Return the maximum value in the generated array.

Key Insights

  • The array generation uses a simulation-based approach.
  • The rules use previously computed values, ensuring that when computing nums[k], the required previous values are available.
  • The maximum value can be tracked on-the-fly or found after array generation.
  • Since n is at most 100, a simple iterative solution is efficient.

Space and Time Complexity

Time Complexity: O(n) because we iterate from 2 to n. Space Complexity: O(n) for storing the generated array.

Solution

We simulate the array generation process as described. We start with an array of size n + 1 where the first two elements are predefined (0 and 1), then compute subsequent elements:

  • For even indices: nums[2 * i] = nums[i].
  • For odd indices: nums[2 * i + 1] = nums[i] + nums[i + 1]. After constructing the array, we traverse it to determine the maximum value. The algorithm uses a simple loop for simulation and a separate loop (or a built-in function) to compute the maximum.

Code Solutions

# Function to generate the maximum value in the array for a given n
def get_maximum_generated(n: int) -> int:
    # Base case when n is 0, simply return 0 because nums = [0]
    if n == 0:
        return 0

    # Create an array for nums with n+1 elements, initializing with zeros
    nums = [0] * (n + 1)
    
    # Set the second element as per the problem definition
    nums[1] = 1
    
    # Generate the array using the provided rules
    for i in range(1, (n // 2) + 1):
        # Compute index for even value if within bounds
        even_index = 2 * i
        if even_index <= n:
            nums[even_index] = nums[i]
        # Compute index for odd value if within bounds
        odd_index = 2 * i + 1
        if odd_index <= n:
            nums[odd_index] = nums[i] + nums[i + 1]
    
    # Return the maximum value in the generated array
    return max(nums)

# Example usage:
print(get_maximum_generated(7))  # Expected output: 3
← Back to All Questions