Categories
Maximizing the Final Element
Date
Author
Given an array of integers, perform certain operations in order to satisfy some constraints. The constraints are as follows:
The first array element must be 1.
For all other elements, the difference between adjacent integers must not be greater than 1. In other words, for 1 ≤ i < n, arr[i] – arr[i-1] ≤ 1.
To accomplish this, the following operations are available:
- Rearrange the elements in any way.
- Reduce any element to any number that is at least 1.
What is the maximum value that can be achieved for the final element of the array by following these operations and constraints?
Example
arr = [3, 1, 3, 4]
- Subtract 1 from the first element, making the array [2, 1, 3, 4].
- Rearrange the array into [1, 2, 3, 4].
- The final element’s value is 4, the maximum value that can be achieved. Therefore, the answer is 4.
Function Description
Complete the function getMaxValue in the editor below.
getMaxValue has the following parameter:
int arr[n]: an array of integers
Returns:
int: the maximum value that can be achieved for the final element of the array given the conditions above
Constraints
1 ≤ n ≤ 105
1 ≤ arr[i] ≤ 109
Input Format For Custom Testing
The first line contains an integer, n, denoting the number of elements in arr.
Each line i of the n subsequent lines (where 0 ≤ i < n) contains an integer describing arr[i].
Sample Case 0
Sample Input For Custom Testing
STDIN Function ----- -------- 4 → arr[] size n = 4 1 → arr = [1, 3, 2, 2] 3 2 2
Sample Output
3
Explanation
These elements can be rearranged to become [1, 2, 2, 3], which results in a maximum value of 3 for the final element. Notice how this array follows the constraints that (1) the first element is 1, and (2) the difference between each pair of adjacent integers is no more than 1.
Sample Case 1
Sample Input For Custom Testing
STDIN Function ----- -------- 4 → arr[] size n = 4 3 → arr = [3, 2, 3, 5] 2 3 5
Sample Output
4
Explanation
These elements can be rearranged to become [2, 3, 3, 5]. Then, the heights can be adjusted to become [1, 2, 3, 4]. Therefore, the maximum value of the final element is 4.
Solution (Python3):
#!/bin/python3
import math
import os
import random
import re
import sys
def getMaxValue(arr):
arr.sort() # Sort the array in ascending order
min_val = 1 # Initialize the minimum value to 1
for i in range(len(arr)):
if arr[i] > min_val:
arr[i] = min_val # Reduce the element to the minimum value if it's greater
min_val = arr[i] + 1 # Update the minimum value for the next element
return arr[-1] # Return the maximum value, which is the last element in the sorted array
# Test the code with the provided sample inputs
arr = [3, 1, 3, 4]
result = getMaxValue(arr)
print(result)
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
arr_count = int(input().strip())
arr = []
for _ in range(arr_count):
arr_item = int(input().strip())
arr.append(arr_item)
result = getMaxValue(arr)
fptr.write(str(result) + '\n')
fptr.close()