-
Notifications
You must be signed in to change notification settings - Fork 0
/
minimize_maximum_of_array.py
34 lines (31 loc) · 1.22 KB
/
minimize_maximum_of_array.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from math import ceil
from typing import List
class Solution:
"""
Task:
You are given a 0-indexed array nums comprising of n non-negative integers.
In one operation, you must:
- Choose an integer i such that 1 <= i < n and nums[i] > 0.
- Decrease nums[i] by 1.
- Increase nums[i - 1] by 1.
Return the minimum possible value of the maximum integer of nums after performing any number of operations.
"""
def minimizeArrayValue(self, nums: List[int]) -> int:
# I. The max possible value between two adjacent elements
# is their average (rounded up).
#
# II. The max between three or more elements
# is the average of largest and smallest.
#
# III. Moving only in one direction (right to left)
# Thus, if the largest is first it cannot be changed
# and elements after largest doesn't count
#
# Thus, return the first if largest or avg between smallest and largest
max_num = sum_num = nums[0]
for i in range(1, len(nums)):
sum_num += nums[i]
avg = ceil(sum_num / (i + 1))
if max_num < avg:
max_num = avg
return max_num