Get Maximum in Generated Array Leetcode Solution

The problem Get Maximum in Generated Array Leetcode Solution provided us with a single integer. With the given single integer, we need to find the maximum integer in the generated array. The array generation has some rules. Under the imposed constraints, we need to find the maximum integer that could have been generated. The rules are:

1. arr[0] = 0, arr[1] = 1
2. arr[2*i] = arr[i] where 2<=2*i<=n
3. and arr[2*i+1] = arr[i] + arr[i+1] where 2<=2*i+1<=n

But before diving any further into the solution. We should take a look at a few examples.

n = 7

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

So, we can see nums = [0,1,1,2,1,3,2,3], and the maximum is 3 among them. Thus the answer is 3.

Approach for Get Maximum in Generated Array Leetcode Solution

The problem Get Maximum in Generated Array Leetcode Solution has some constraints that must be satisfied. Under the given constraints, we are required to find the maximum integer. The rules for the array generation have already been explained in the problem’s description. The first method that comes to mind is the generation of array and finding the maximum element. But will that solve the problem?

If we simply went ahead with the generation we won’t be able to find correct results. Because it depends on how we generate the array. If we generate elements at 2ith and (2i+1) index when we are at ith index. At that moment, we would not have the generated value for (i+1)th index. In that case, the result will not be accurate.

To solve the problem, we will manipulate the formulae for element generation. If we replace i with i-1, in the 3rd rule. we find that arr[2*i-1] = arr[i] + arr[i-1]. So, now we can use the rules for array generation. Because this rule uses the value of already generated value. So here instead of using any future unknown values we are using the pre-calculated values. So now we simply simulate the whole process using a for loop and checking if 2*i and 2*i-1 are in the bounds of the array. Once this is confirmed, we use the formulas to fill the array.

Code

C++ code for Get Maximum in Generated Array Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

int getMaximumGenerated(int n) {
    if(n == 0)return 0;
    if(n == 1)return 1;
    vector<int> tmp(n+1);
    tmp[0] = 0;
    tmp[1] = 1;
    for(int i=1;i<=n;i++){
        if(2*i<=n)
            tmp[2*i] = tmp[i];
        if(2*i-1<=n)
            tmp[2*i-1] = tmp[i] + tmp[i-1];
    }
    int ans = 0;
    for(int i=0;i<=n;i++)
        ans = max(tmp[i], ans);
    return ans;
}

int main(){
    cout<<getMaximumGenerated(7);
}

3

Java code for Get Maximum in Generated Array Leetcode Solution

import java.util.*;
import java.io.*;

class Main {

    public static int getMaximumGenerated(int n) {
        if(n == 0)return 0;
        if(n == 1)return 1;
        int[] tmp = new int[n+1];
        tmp[0] = 0;
        tmp[1] = 1;
        for(int i=1;i<=n;i++){
            if(2*i<=n)
                tmp[2*i] = tmp[i];
            if(2*i-1<=n)
                tmp[2*i-1] = tmp[i] + tmp[i-1];
        }
        int ans = 0;
        for(int i=0;i<=n;i++)
            ans = Math.max(tmp[i], ans);
        return ans;
    }

    public static void main(String[] args){
        System.out.println(getMaximumGenerated(7));
    }
}

3

Complexity Analysis

Time Complexity

O(N), because we generate all of the n elements.

Space Complexity

O(N), because we created a temporary array to store the array values.