Get Maximum in Generated Array

Difficulty: Easy | Acceptance: 51.50% | Paid: No Topics: Array, Simulation

You are given an integer n. An 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.

• Examples
• Constraints
• Iterative Simulation
• Recursive with Memoization

Examples

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

Input: n = 2
Output: 1
Explanation: According to the given rules:
  nums[0] = 0
  nums[1] = 1
  nums[(1 * 2) = 2] = nums[1] = 1
Hence, nums = [0,1,1], and the maximum is 1.

Input: n = 3
Output: 2
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
Hence, nums = [0,1,1,2], and the maximum is 2.

Constraints

0 <= n <= 100

Iterative Simulation

Intuition The problem defines the array elements based on specific rules derived from their indices. We can simulate this process by iterating through the indices and filling the array values according to the given formulas, keeping track of the maximum value encountered.

Steps

• Handle the edge case where n is 0 by returning 0.
• Initialize an array nums of size n + 1 with zeros.
• Set nums[1] = 1 and initialize max_val to 1.
• Iterate i from 1 up to n // 2.
• For each i, if 2 * i is within bounds, set nums[2 * i] = nums[i] and update max_val.
• If 2 * i + 1 is within bounds, set nums[2 * i + 1] = nums[i] + nums[i + 1] and update max_val.
• Return max_val.

class Solution:
    def getMaximumGenerated(self, n: int) -> int:
        if n == 0:
            return 0
        
        nums = [0] * (n + 1)
        nums[1] = 1
        max_val = 1
        
        for i in range(1, n // 2 + 1):
            if 2 * i <= n:
                nums[2 * i] = nums[i]
                max_val = max(max_val, nums[2 * i])
            
            if 2 * i + 1 <= n:
                nums[2 * i + 1] = nums[i] + nums[i + 1]
                max_val = max(max_val, nums[2 * i + 1])
        
        return max_val

Complexity

• Time: O(n)
• Space: O(n)
• Notes: We use O(n) space to store the array. This is the most straightforward approach.

Recursive with Memoization

Intuition The definition of nums[i] is recursive in nature. We can define a function that calculates nums[i] recursively. To avoid the exponential time complexity of a naive recursive solution, we use memoization to store computed values.

Steps

• Handle the edge case where n is 0.
• Initialize a memoization array of size n + 1 with 0.
• Set memo[1] = 1.
• Define a recursive helper function get(i).
• Base cases: if i is 0 return 0, if i is 1 return 1.
• If memo[i] is already computed (non-zero), return it.
• If i is even, memo[i] = get(i / 2).
• If i is odd, memo[i] = get(i // 2) + get(i // 2 + 1).
• Iterate from 2 to n, calling get(i) and tracking the maximum value.

class Solution:
    def getMaximumGenerated(self, n: int) -> int:
        if n == 0:
            return 0
        
        memo = [0] * (n + 1)
        memo[1] = 1
        
        def get(i):
            if i == 0:
                return 0
            if i == 1:
                return 1
            if memo[i] != 0:
                return memo[i]
            
            if i % 2 == 0:
                memo[i] = get(i // 2)
            else:
                memo[i] = get(i // 2) + get(i // 2 + 1)
            
            return memo[i]
        
        max_val = 1
        for i in range(2, n + 1):
            max_val = max(max_val, get(i))
        
        return max_val

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Each index is computed only once, leading to linear time. Space is used for the memoization array and the recursion stack.