Get Maximum in Generated Array - Practice Coding Problems

Get Maximum in Generated Array - Problem

Array Simulation Easy

You are given an integer n. A 0-indexed integer 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.

Input & Output

Example 1 — Basic Case

$ Input: n = 7

› Output: 3

💡 Note: nums = [0,1,1,2,1,3,2,3]. Generated by rules: nums[2]=nums[1]=1, nums[3]=nums[1]+nums[2]=2, nums[4]=nums[2]=1, nums[5]=nums[2]+nums[3]=3, nums[6]=nums[3]=2, nums[7]=nums[3]+nums[4]=3. Maximum is 3.

Example 2 — Small Input

$ Input: n = 2

› Output: 1

💡 Note: nums = [0,1,1]. nums[2] = nums[1] = 1. Maximum is 1.

Example 3 — Edge Case

$ Input: n = 0

› Output: 0

💡 Note: nums = [0]. Only element is 0, so maximum is 0.

Constraints

0 ≤ n ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Given integer n = 7

Generate

Build array using generation rules

Output

Return maximum value found: 3

Key Takeaway

🎯 Key Insight: Simulate the array generation process while tracking the maximum value encountered

Asked in

a Amazon 25 M Microsoft 20

The key insight is to recognize this as a simulation problem where we build the array following given rules and track the maximum. The optimal approach tracks the maximum while generating elements in a single pass. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Track Maximum While Generating	O(n)	O(n)	Generate array elements while tracking maximum in single pass
Generate Array Then Find Maximum	O(n)	O(n)	Generate the complete array according to rules, then find maximum

Track Maximum While Generating — Algorithm Steps

Initialize array and maxVal = 0
For each index, generate value using rules and update maxVal if needed
Return the tracked maximum value

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set nums[0] = 0, maxVal = 0, handle n >= 1 case

Generate + Track

Generate each element and update maxVal immediately

Result

Return tracked maximum without extra scan

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int solution(int n) {
    if (n == 0) return 0;
    
    int* nums = (int*)malloc((n + 1) * sizeof(int));
    nums[0] = 0;
    int maxVal = 0;
    
    if (n >= 1) {
        nums[1] = 1;
        maxVal = 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];
        }
        
        if (nums[i] > maxVal) {
            maxVal = nums[i];
        }
    }
    
    free(nums);
    return maxVal;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to generate n elements while tracking maximum

✓ Linear Growth

Space Complexity

O(n)

Store the complete array of n+1 elements

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~10 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Track Maximum While Generating — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler