Get Maximum in Generated Array

Easy
0/40
profile
Contributed by
2 upvotes

Problem statement

Given an integer ‘N’. We want to find the maximum element of the array ‘Arr’ of length ‘N’+1 which can be generated as per the following rules:

Arr[0] = 0
Arr[1] = 1
Arr[2 * i] = Arr[i] when 2 ≤ 2 * i ≤ N
Arr[2 * i + 1] = Arr[i] + Arr[i + 1] when 2 ≤ 2 * i + 1 ≤ N
For example: 
Suppose ‘N’ = 5, then
Arr[0] = 0
Arr[1] = 1
Arr[2] = Arr[2 * 1] = Arr[1] = 1
Arr[3] = Arr[2 * 1 + 1] = Arr[1] + Arr[2] = 2
Arr[4] = Arr[2 * 2] = Arr[2] = 1
Arr[5] = Arr[2 * 2 + 1] = Arr[2] + Arr[3] = 3

Now we have constructed the ‘Arr’ Array of size ‘N’+1 according to the rules stated in the problem description.
So, Arr = [0, 1, 1, 2, 1, 3] and maximum of its elements is 3.
Hence our output will be 3.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains a single integer ‘T’ representing the no. of test cases.

The first line of each test case contains a single integer ‘N’, where ‘N’+1 denotes the size of ‘Arr’.

Output Format:

For each test case, print a single integer value denoting the maximum element of ‘Arr’.

Print a separate line for each test case.
Note 
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints -

1 ≤ T ≤ 1000
1 ≤ N ≤ 100000
ΣN ≤ 200000

Time limit: 1 Sec
Sample Input 1 :
2
5
4
Sample Output 1 :
3
2
Explanation For Sample Input 1 :
For First Case - Same as explained in above example.

For the second case - 
N = 4
Arr[0] = 0
Arr[1] = 1
Arr[2] = Arr[2 * 1] = Arr[1] = 1
Arr[3] = Arr[2 * 1 + 1] = Arr[1] + Arr[2] = 2
Arr[4] = Arr[2 * 2] = Arr[2] = 1
So, Arr = [0, 1, 1, 2, 1] and maximum of its elements is 2.
Hence our output will be 2.
Sample Input 2 :
2
7
10
Sample Output 2 :
3
4
Hint

We can traverse and calculate each element of ‘Arr’ as per the given rules.

Approaches (1)
Brute Force (DP)

We will just implement as per the rules. We will declare an array of size ‘N’+1. We will iterate over indexes from 0 to n and fill the Arr[index] values as per the given rules. Implementation details will be as per the following algorithm.

 

Algorithm: 

 

Steps are as follows:

  • If n == 0
    • Return 0
  • Declare an integer array ‘Arr’ of size ‘N’+1
  • Set Arr[0] = 0
  • Set Arr[1] = 1
  • Declare an integer variable “Ans” and set it to 1
  • Iterate over i from 2 to n inclusive
    • j = i/2 (rounded down)
    • If i is odd
      • Arr[i] = Arr[j] + Arr[j+1]
    • Else if i is even
      • Arr[i] = Arr[j]
    • Ans = max(Ans, Arr[i])
  • Return Ans
Time Complexity

O(N) where ‘N’ is the given input.

 

We will be iterating and generating the whole ‘Arr’ array. Each term will take O(1) time to iterate. So for total O(N) terms, we will have total time complexity of O(N) * O(1) = O(N).

Space Complexity

O(N) where ‘N’ is the given input.

 

We need space for the array ‘Arr’ and the ‘Ans’ variable. So, total space will be O(N) + O(1) = O(N).

Code Solution
(100% EXP penalty)
Get Maximum in Generated Array
Full screen
Console