Get Maximum In Generated Array - Leetcode Solution

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

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, the maximum value in nums is 3.

Approach:

We can directly find the maximum element from the array by iterating through all the elements but this approach will take O(n) time. We can optimize the approach with a better approach.

In the given array, the element at the ith index can be found using the following two cases:

Case 1: For an even index i, nums[i] = nums[i/2]. Case 2: For an odd index i, nums[i] = nums[i/2] + nums[i/2 + 1].

To find the maximum value in the array, we can create an array of size n+1 and then follow the given algorithm to calculate element at each index. We can also keep track of the maximum element calculated till now, and return it as the answer.

Algorithm:

1. Create an array of size n+1, which is initialized with 0.
2. Initialize the first two elements of the array with 0 and 1, respectively.
3. Traverse through the array from index 2 to n. i. If the index i is even, set the value of nums[i] to nums[i/2]. ii. If the index i is odd, set the value of nums[i] to nums[i/2] + nums[i/2 + 1].
4. Keep a track of the maximum value till now and update it whenever we encounter a new maximum value.
5. Return the maximum value found.

Time Complexity: The time complexity of the algorithm is O(n) since we are traversing through all the elements of the array.

Space Complexity: The space complexity of the algorithm is O(n) since we are using an extra array of size n+1.

Solution:

class Solution { public: int getMaximumGenerated(int n) { if (n == 0) return 0; vector<int> nums(n+1, 0); nums[1] = 1; int maxNum = 1; for(int i=2; i<=n; i++){ if(i%2==0) nums[i] = nums[i/2]; else nums[i] = nums[i/2] + nums[i/2 + 1]; maxNum = max(maxNum, nums[i]); } return maxNum; } };

The time complexity of the above solution is O(n) and the space complexity is O(n).

1