Get Maximum in Generated Array
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]when2 <= 2 * i <= n -
nums[2 * i + 1] = nums[i] + nums[i + 1]when2 <= 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, nums = [0,1,1,2,1,3,2,3], and the maximum is 3.
Example 2:
Input: n = 2 Output: 1 Explanation: According to the given rules, the maximum between nums[0], nums[1], and nums[2] is 1.
Example 3:
Input: n = 3 Output: 2 Explanation: According to the given rules, the maximum between nums[0], nums[1], nums[2], and nums[3] is 2.
Constraints:
-
0 <= n <= 100
Solution :
class Solution {
public int getMaximumGenerated(int n) {
if(n==0)
return 0;
else if(n==1)
return 1;
int nums[] = new int[n+1];
nums[0] = 0;
nums[1] = 1;
int i, max =0;
for(i=2;i<=n;i++){
if(i % 2 == 0){
nums [i] =
nums[i/2];
}
else{
nums[i] = nums[i/2]
+ nums[i/2+1];
}
max = Math.max(nums[i], max);
}
return max;
}
}
Note:
Here, the problem itself clearly give you a solution. The solution for this
problem can applied directly as explained in the problem [change only i value
as explained in input 1]. But, if you follow this approach, there will be
occurrence of error if n value is even[as explained in input 1, but n is
even].
So, we need to approach the problem in different way.
1) Create a nums array with a size of n+1.
2) Initialize default values for nums[0] and nums[1].
3)For i>=2 till n,
a)If i is even, then nums [i] = nums[i/2]
b) If i is odd, then nums [i] = nums[i/2] + nums[i/2+1] (By using i/2, we can get values as represented in problem statement)
c)For each nums[i], update max variable.
4) Finally return max.
Related Posts:
Like us? Please do share with your friends ..!!
Follow us to receive updates instantly.
If you have any feedback/suggestions, leave it in a comment section or contact us through our contact page which will be helpful for us to improve.
Comments
Post a Comment