Tasks Details
medium
Divide array A into K blocks and minimize the largest sum of any block.
Task Score
100%
Correctness
100%
Performance
100%
You are given integers K, M and a non-empty array A consisting of N integers. Every element of the array is not greater than M.
You should divide this array into K blocks of consecutive elements. The size of the block is any integer between 0 and N. Every element of the array should belong to some block.
The sum of the block from X to Y equals A[X] + A[X + 1] + ... + A[Y]. The sum of empty block equals 0.
The large sum is the maximal sum of any block.
For example, you are given integers K = 3, M = 5 and array A such that:
A[0] = 2 A[1] = 1 A[2] = 5 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 2The array can be divided, for example, into the following blocks:
- [2, 1, 5, 1, 2, 2, 2], [], [] with a large sum of 15;
- [2], [1, 5, 1, 2], [2, 2] with a large sum of 9;
- [2, 1, 5], [], [1, 2, 2, 2] with a large sum of 8;
- [2, 1], [5, 1], [2, 2, 2] with a large sum of 6.
The goal is to minimize the large sum. In the above example, 6 is the minimal large sum.
Write a function:
def solution(K, M, A)
that, given integers K, M and a non-empty array A consisting of N integers, returns the minimal large sum.
For example, given K = 3, M = 5 and array A such that:
A[0] = 2 A[1] = 1 A[2] = 5 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 2the function should return 6, as explained above.
Write an efficient algorithm for the following assumptions:
- N and K are integers within the range [1..100,000];
- M is an integer within the range [0..10,000];
- each element of array A is an integer within the range [0..M].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 2 minutes
Notes
not defined yet
Code: 18:04:28 UTC,
java,
autosave
Code: 18:04:28 UTC,
java,
autosave
Code: 18:04:33 UTC,
py,
verify,
result: Failed
def is_valid_minimal_limit(A, num_blocks, sum_slice_limit):
"""
Scans Array A summing values until minimal_limit is reached. Array A cannot
be divided into more than num_blocks. If the parameters given cannot succeed
then a False is returned.
"""
block_count = 0
block_sum = 0
for number in A:
new = block_sum + number
if new <= sum_slice_limit: # We have not breached the block sum limit
block_sum = new
else: # We have breached the block sum limit
block_count += 1
block_sum = number
if block_count >= num_blocks:
return False
return True
def binary_search(A, num_blocks):
"""
When array is divided into num_blocks the sum of each block searched to find
the minimal highest block value.
"""
sum_slice_min = max(A)
sum_slice_max = sum(A)
while sum_slice_min <= sum_slice_max:
sum_slice_mid = (sum_slice_min + sum_slice_max) // 2
#print(sum_slice_mid)
if is_valid_minimal_limit(A, num_blocks, sum_slice_mid):
sum_slice_max = sum_slice_mid - 1 # Search the lower half of the space
else:
sum_slice_min = sum_slice_mid + 1 # Search the upper half of the space
return sum_slice_min
def solution(A, N, M):
# Using M as the assumed max value of array A doesn't work!!!
return binary_search(A, N)
Analysis
expand all
Example tests
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last):
File "exec.py", line 137, in <module>
main()
File "exec.py", line 99, in main
result = solution( K, M, A )
File "/tmp/solution.py", line 41, in solution
return binary_search(A, N)
File "/tmp/solution.py", line 26, in binary_search
sum_slice_min = max(A)
TypeError: 'int' object is not iterable
Code: 18:04:59 UTC,
py,
autosave
def is_valid_minimal_limit(A, num_blocks, sum_slice_limit):
"""
Scans Array A summing values until minimal_limit is reached. Array A cannot
be divided into more than num_blocks. If the parameters given cannot succeed
then a False is returned.
"""
block_count = 0
block_sum = 0
for number in A:
new = block_sum + number
if new <= sum_slice_limit: # We have not breached the block sum limit
block_sum = new
else: # We have breached the block sum limit
block_count += 1
block_sum = number
if block_count >= num_blocks:
return False
return True
def binary_search(A, num_blocks):
"""
When array is divided into num_blocks the sum of each block searched to find
the minimal highest block value.
"""
sum_slice_min = max(A)
sum_slice_max = sum(A)
while sum_slice_min <= sum_slice_max:
sum_slice_mid = (sum_slice_min + sum_slice_max) // 2
#print(sum_slice_mid)
if is_valid_minimal_limit(A, num_blocks, sum_slice_mid):
sum_slice_max = sum_slice_mid - 1 # Search the lower half of the space
else:
sum_slice_min = sum_slice_mid + 1 # Search the upper half of the space
return sum_slice_min
def solution(K,M, M):
# Using M as the assumed max value of array A doesn't work!!!
return binary_search(A, N)
Code: 18:05:10 UTC,
py,
autosave
def is_valid_minimal_limit(A, num_blocks, sum_slice_limit):
"""
Scans Array A summing values until minimal_limit is reached. Array A cannot
be divided into more than num_blocks. If the parameters given cannot succeed
then a False is returned.
"""
block_count = 0
block_sum = 0
for number in A:
new = block_sum + number
if new <= sum_slice_limit: # We have not breached the block sum limit
block_sum = new
else: # We have breached the block sum limit
block_count += 1
block_sum = number
if block_count >= num_blocks:
return False
return True
def binary_search(A, num_blocks):
"""
When array is divided into num_blocks the sum of each block searched to find
the minimal highest block value.
"""
sum_slice_min = max(A)
sum_slice_max = sum(A)
while sum_slice_min <= sum_slice_max:
sum_slice_mid = (sum_slice_min + sum_slice_max) // 2
#print(sum_slice_mid)
if is_valid_minimal_limit(A, num_blocks, sum_slice_mid):
sum_slice_max = sum_slice_mid - 1 # Search the lower half of the space
else:
sum_slice_min = sum_slice_mid + 1 # Search the upper half of the space
return sum_slice_min
def solution(K, M, A):
# Using M as the assumed max value of array A doesn't work!!!
return binary_search(A, K)
Code: 18:05:11 UTC,
py,
verify,
result: Passed
def is_valid_minimal_limit(A, num_blocks, sum_slice_limit):
"""
Scans Array A summing values until minimal_limit is reached. Array A cannot
be divided into more than num_blocks. If the parameters given cannot succeed
then a False is returned.
"""
block_count = 0
block_sum = 0
for number in A:
new = block_sum + number
if new <= sum_slice_limit: # We have not breached the block sum limit
block_sum = new
else: # We have breached the block sum limit
block_count += 1
block_sum = number
if block_count >= num_blocks:
return False
return True
def binary_search(A, num_blocks):
"""
When array is divided into num_blocks the sum of each block searched to find
the minimal highest block value.
"""
sum_slice_min = max(A)
sum_slice_max = sum(A)
while sum_slice_min <= sum_slice_max:
sum_slice_mid = (sum_slice_min + sum_slice_max) // 2
#print(sum_slice_mid)
if is_valid_minimal_limit(A, num_blocks, sum_slice_mid):
sum_slice_max = sum_slice_mid - 1 # Search the lower half of the space
else:
sum_slice_min = sum_slice_mid + 1 # Search the upper half of the space
return sum_slice_min
def solution(K, M, A):
# Using M as the assumed max value of array A doesn't work!!!
return binary_search(A, K)
Analysis
Code: 18:05:34 UTC,
py,
verify,
result: Passed
def is_valid_minimal_limit(A, num_blocks, sum_slice_limit):
"""
Scans Array A summing values until minimal_limit is reached. Array A cannot
be divided into more than num_blocks. If the parameters given cannot succeed
then a False is returned.
"""
block_count = 0
block_sum = 0
for number in A:
new = block_sum + number
if new <= sum_slice_limit: # We have not breached the block sum limit
block_sum = new
else: # We have breached the block sum limit
block_count += 1
block_sum = number
if block_count >= num_blocks:
return False
return True
def binary_search(A, num_blocks):
"""
When array is divided into num_blocks the sum of each block searched to find
the minimal highest block value.
"""
sum_slice_min = max(A)
sum_slice_max = sum(A)
while sum_slice_min <= sum_slice_max:
sum_slice_mid = (sum_slice_min + sum_slice_max) // 2
#print(sum_slice_mid)
if is_valid_minimal_limit(A, num_blocks, sum_slice_mid):
sum_slice_max = sum_slice_mid - 1 # Search the lower half of the space
else:
sum_slice_min = sum_slice_mid + 1 # Search the upper half of the space
return sum_slice_min
def solution(K, M, A):
# Using M as the assumed max value of array A doesn't work!!!
return binary_search(A, K)
Analysis
Code: 18:05:36 UTC,
py,
final,
score:
100
def is_valid_minimal_limit(A, num_blocks, sum_slice_limit):
"""
Scans Array A summing values until minimal_limit is reached. Array A cannot
be divided into more than num_blocks. If the parameters given cannot succeed
then a False is returned.
"""
block_count = 0
block_sum = 0
for number in A:
new = block_sum + number
if new <= sum_slice_limit: # We have not breached the block sum limit
block_sum = new
else: # We have breached the block sum limit
block_count += 1
block_sum = number
if block_count >= num_blocks:
return False
return True
def binary_search(A, num_blocks):
"""
When array is divided into num_blocks the sum of each block searched to find
the minimal highest block value.
"""
sum_slice_min = max(A)
sum_slice_max = sum(A)
while sum_slice_min <= sum_slice_max:
sum_slice_mid = (sum_slice_min + sum_slice_max) // 2
#print(sum_slice_mid)
if is_valid_minimal_limit(A, num_blocks, sum_slice_mid):
sum_slice_max = sum_slice_mid - 1 # Search the lower half of the space
else:
sum_slice_min = sum_slice_mid + 1 # Search the upper half of the space
return sum_slice_min
def solution(K, M, A):
# Using M as the assumed max value of array A doesn't work!!!
return binary_search(A, K)Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N*log(N+M))
expand all
Correctness tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.036 s
OK
6.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.040 s
OK
expand all
Performance tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
1.
0.068 s
OK
2.
0.072 s
OK
3.
0.080 s
OK
4.
0.080 s
OK
1.
0.092 s
OK
2.
0.096 s
OK
3.
0.096 s
OK
4.
0.096 s
OK
1.
0.416 s
OK
2.
0.428 s
OK
3.
0.428 s
OK
4.
0.444 s
OK
1.
0.268 s
OK
2.
0.284 s
OK
3.
0.292 s
OK
4.
0.288 s
OK
1.
0.384 s
OK
2.
0.456 s
OK
3.
0.424 s
OK
4.
0.520 s
OK