1646. Get Maximum in Generated Array
Problem Description
In this problem, you need to work with a special array generation rule to find the maximum element in the generated array. An integer n
is given which determines the size of an integer array nums
of length n + 1
. The array nums
is constructed following specific rules:
nums[0]
is set to0
.nums[1]
is set to1
.- For each even index
2i
where2 <= 2i <= n
, the value isnums[2i] = nums[i]
. - For each odd index
2i + 1
where2 <= 2i + 1 <= n
, the value isnums[2i + 1] = nums[i] + nums[i + 1]
.
Your goal is to return the maximum integer value that exists in the array nums
.
Intuition
Intuitively, the problem can be solved by directly applying the given generation rules to construct the array and then find the maximum value in it. Since the maximum number generated is a result of the addition in the sequence, one would expect it to appear at an odd index because all odd indices are created by summing two elements of the array.
We can observe that each element is derived from previously calculated values. This gives us a hint that we should approach the problem iteratively, constructing the array one number at a time and making use of previously computed elements. This iterative approach ensures that we use O(n) time complexity because each element calculation requires constant time.
Additionally, we can see that the array follows a repetitive pattern based on even and odd indices, which means we can use bitwise operations for efficiency. Notably, when working with an index i
, i >> 1
is equivalent to i//2
, which we need for calculating even indices. For odd indices, we use i >> 1
(the same as i//2
) and (i >> 1) + 1
(the same as i//2 + 1
).
Using this approach, we create and fill the array nums
up to index n
and simply return the maximum value in the array as our solution. Here space complexity is O(n) because we need to store n + 1
elements in the array nums
.
Learn more about Dynamic Programming patterns.
Solution Approach
The implementation of the solution follows a straightforward approach based on the rules for generating the array. This solution uses the iterative method to populate the array based on the two conditions for even and odd indices. Let's break down the solution step by step:
-
Initialize the
nums
array withn + 1
elements, as the length of the array is determined by the inputn
. Initialize all elements to0
. -
Since the first two elements
nums[0]
andnums[1]
are already given by the problem (0 and 1, respectively), we manually set them. This serves as a base case for building up the rest of the array. -
Iterate over the range from
2
ton
, inclusive. We divide this process into two cases:- When
i
is even (i % 2 == 0
), we setnums[i]
tonums[i >> 1]
. The bitwise right shift operation "i >> 1
" effectively dividesi
by 2. - When
i
is odd, we setnums[i]
to the sum ofnums[i >> 1]
andnums[(i >> 1) + 1]
, essentially summing the elements at indicesi//2
andi//2 + 1
.
- When
-
After we've populated the
nums
array, we return the maximum integer from it using Python's built-inmax()
function.
In terms of data structures, we only use a list to store the sequence, and no additional data structures are needed. As the process involves simple arithmetic and assignment operations, the algorithm doesn't make use of complex patterns. It's an imperative, step-by-step generation of the sequence values using conditions for even and odd integers, followed by a quest for the maximum value.
The time complexity of this solution is O(n), as we iterate over the range once and the max function also traverses the list with complexity O(n). The space complexity is O(n) as well, due to the storage requirements for the nums
array.
Here is the implementation of our solution:
class Solution:
def getMaximumGenerated(self, n: int) -> int:
if n < 2:
return n
nums = [0] * (n + 1)
nums[1] = 1
for i in range(2, n + 1):
# Populate nums[i] based on even/odd index
nums[i] = nums[i >> 1] if i % 2 == 0 else nums[i >> 1] + nums[(i >> 1) + 1]
# Return the max value from the generated array
return max(nums)
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose we have n = 7
. We want to generate the nums
array according to the rules and find the maximum element.
-
We initialize
nums
withn + 1
(8) elements:nums = [0, 0, 0, 0, 0, 0, 0, 0]
. -
We set
nums[0]
to0
andnums[1]
to1
as given:nums = [0, 1, 0, 0, 0, 0, 0, 0]
. -
We start iterating from index
2
to7
:- For
i = 2
(even), we use the formulanums[2] = nums[2 >> 1]
, which isnums[2] = nums[1]
, sonums[2] = 1
. - For
i = 3
(odd),nums[3] = nums[3 >> 1] + nums[(3 >> 1) + 1]
, which isnums[3] = nums[1] + nums[2]
, sonums[3] = 2
. - For
i = 4
(even),nums[4] = nums[4 >> 1]
, which isnums[4] = nums[2]
, sonums[4] = 1
. - For
i = 5
(odd),nums[5] = nums[5 >> 1] + nums[(5 >> 1) + 1]
, which isnums[5] = nums[2] + nums[3]
, sonums[5] = 3
. - For
i = 6
(even),nums[6] = nums[6 >> 1]
, which isnums[6] = nums[3]
, sonums[6] = 2
. - For
i = 7
(odd),nums[7] = nums[7 >> 1] + nums[(7 >> 1) + 1]
, which isnums[7] = nums[3] + nums[4]
, sonums[7] = 3
.
- For
-
Now our
nums
array looks like this:nums = [0, 1, 1, 2, 1, 3, 2, 3]
. -
The final step is to return the maximum value in
nums
, which is3
.
This example follows the solution approach step by step to generate the nums
array and then uses the built-in max()
function to find the maximum element, which is the objective of our problem. The unit of work done for each iteration illustrates the O(n) time complexity of generating the array. The space complexity is also illustrated with the array holding n + 1
= 8 elements in this example.
Solution Implementation
1class Solution:
2 def get_maximum_generated(self, n: int) -> int:
3 # If the input is less than two, return the input as it is.
4 if n < 2:
5 return n
6
7 # Initialize the array with zeros and set the second element to one.
8 generated_nums = [0] * (n + 1)
9 generated_nums[1] = 1
10
11 # Generate the array using the given rules.
12 for i in range(2, n + 1):
13 if i % 2 == 0:
14 # For even indices, the value at the index is equal to
15 # the value in the array at half the index.
16 generated_nums[i] = generated_nums[i // 2]
17 else:
18 # For odd indices, the value at the index is the sum of
19 # the values in the array at half the index and one more than half.
20 generated_nums[i] = generated_nums[i // 2] + generated_nums[(i // 2) + 1]
21
22 # Return the maximum value from the generated array.
23 return max(generated_nums)
24
1import java.util.Arrays;
2
3class Solution {
4
5 public int getMaximumGenerated(int n) {
6 // Handle the base cases where n is 0 or 1.
7 if (n < 2) {
8 return n;
9 }
10
11 // Initialize an array to store the generated numbers.
12 int[] generatedNumbers = new int[n + 1];
13 // According to the problem statement, nums[1] should be 1.
14 generatedNumbers[1] = 1;
15
16 // Populate the array based on the given rules.
17 for (int i = 2; i <= n; ++i) {
18 // If i is even, the number is generated using the formula nums[i/2].
19 if (i % 2 == 0) {
20 generatedNumbers[i] = generatedNumbers[i / 2];
21 } else {
22 // If i is odd, the number is generated using the sum of nums[i/2] and nums[i/2 + 1].
23 generatedNumbers[i] = generatedNumbers[i / 2] + generatedNumbers[i / 2 + 1];
24 }
25 }
26
27 // Return the maximum number from the array using Java Streams.
28 return Arrays.stream(generatedNumbers).max().getAsInt();
29 }
30}
31
1class Solution {
2public:
3 // Function to compute the maximum value in the generated array based on the given rules.
4 int getMaximumGenerated(int n) {
5 // Handle the base case where n is less than 2.
6 if (n < 2) {
7 return n;
8 }
9
10 // Initialize the array with enough space to hold values up to index n.
11 vector<int> generatedNums(n + 1);
12
13 // The first two values are given.
14 generatedNums[0] = 0;
15 generatedNums[1] = 1;
16
17 // Populate the array based on the given rule:
18 // If i is even, then generatedNums[i] = generatedNums[i / 2].
19 // If i is odd, then generatedNums[i] = generatedNums[i / 2] + generatedNums[i / 2 + 1].
20 for (int i = 2; i <= n; ++i) {
21 if (i % 2 == 0) {
22 // i is even: use the formula for even indices.
23 generatedNums[i] = generatedNums[i / 2];
24 } else {
25 // i is odd: use the formula for odd indices.
26 generatedNums[i] = generatedNums[i / 2] + generatedNums[i / 2 + 1];
27 }
28 }
29
30 // Find and return the maximum element in the array.
31 return *max_element(generatedNums.begin(), generatedNums.end());
32 }
33};
34
1function getMaximumGenerated(n: number): number {
2 // If the input is 0, the maximum generated value is 0.
3 if (n === 0) {
4 return 0;
5 }
6
7 // Create an array initialized with zeros to store the generated values.
8 const generatedArray: number[] = new Array(n + 1).fill(0);
9 // Base case: the second element in the array is always 1.
10 generatedArray[1] = 1;
11
12 // Loop over each index starting from 2 and populate the array following the rules.
13 for (let index = 2; index <= n; index++) {
14 if (index % 2 === 0) {
15 // If the index is even, the value is the same as the value at half the index.
16 generatedArray[index] = generatedArray[index / 2];
17 } else {
18 // If the index is odd, the value is the sum of values at the floor of half the index and one more than that.
19 const halfIndex = Math.floor(index / 2);
20 generatedArray[index] = generatedArray[halfIndex] + generatedArray[halfIndex + 1];
21 }
22 }
23
24 // Find and return the maximum value in the generated array.
25 return Math.max(...generatedArray);
26}
27
Time and Space Complexity
The given Python code generates an array of integers according to specific generation rules and returns the maximum value in the array for a given n
.
-
Time Complexity: The time complexity of the code is
O(n)
. This is because the for loop runs from 2 ton
, and each operation inside the loop (calculatingnums[i]
and referencing previously computed values) takes constant time. -
Space Complexity: The space complexity of the code is also
O(n)
. This is due to the allocation of a listnums
of sizen + 1
, where each element is initialized and potentially modified as the for loop executes. No auxiliary space that depends onn
is used besides this list.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!