Tasks Details
medium
Given a 3x3 matrix, find the nearest matrix, the sum of whose elements in each row and column is equal.
Task Score
100%
Correctness
100%
Performance
100%
You are given a matrix, consisting of three rows and three columns, represented as an array A of nine integers. The rows of the matrix are numbered from 0 to 2 (from top to bottom) and the columns are numbered from 0 to 2 (from left to right). The matrix element in the J-th row and K-th column corresponds to the array element A[J*3 + K]. For example, the matrix below corresponds to array [0, 2, 3, 4, 1, 1, 1, 3, 1].
![[0 2 3]
[4 1 1]
[1 3 1]](https://codility-frontend-prod.s3.amazonaws.com/media/task_static/almost_magic_square/static/images/auto/90a1e1ad6a523c680991ddd2d7fdf063.png)
In one move you can increment any element by 1.
Your task is to find a matrix whose elements in each row and each column sum to an equal value, which can be constructed from the given matrix in a minimal number of moves.
Write a function:
fun solution(A: IntArray): IntArray
that, given an array A of nine integers, returns an array of nine integers, representing the matrix described above. If there are several possible answers, the function may return any of them.
Examples:
1. Given A = [0, 2, 3, 4, 1, 1, 1, 3, 1], the function could return [1, 2, 3, 4, 1, 1, 1, 3, 2]. The sum of elements in each row and each column of the returned matrix is 6. Two increments by 1 are enough. You can increment A[0] and A[8] (top-left and bottom-right matrix elements). This gives [1, 2, 3, 4, 1, 1, 1, 3, 2], which satisfies the statement's conditions. Alternatively, you can increment A[2] and A[6] (top-right and bottom-left matrix elements). This gives another correct solution: [0, 2, 4, 4, 1, 1, 2, 3, 1].
![[0 2 3]
[4 1 1]
[1 3 1]](https://codility-frontend-prod.s3.amazonaws.com/media/task_static/almost_magic_square/static/images/auto/01335d3771bd0219656f4c4d593af79c.png)
![[0 2 3]
[4 1 1]
[1 3 1]](https://codility-frontend-prod.s3.amazonaws.com/media/task_static/almost_magic_square/static/images/auto/7515378444fd22edb650da0bfadcf67e.png)
2. Given A = [1, 1, 1, 2, 2, 1, 2, 2, 1], the function should return [1, 1, 3, 2, 2, 1, 2, 2, 1]. The sum of elements in each row and each column of the returned matrix is 5. Two increments by 1 are enough. You can increment A[2] (top-right matrix element) twice. In this case, there are no other correct solutions.
![[1 1 1]
[2 2 1]
[2 2 1]](https://codility-frontend-prod.s3.amazonaws.com/media/task_static/almost_magic_square/static/images/auto/4c283f4b5062ed7b1a43a584f36328c7.png)
Write an efficient algorithm for the following assumptions:
- array A contains nine elements;
- each element of array A is an integer within the range [0..100,000,000].
Copyright 2009–2025 by Codility Limited.
All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Kotlin
Time spent on task 2 minutes
Notes
not defined yet
Code: 12:13:04 UTC,
java,
autosave
Code: 12:13:05 UTC,
java,
autosave
Code: 12:13:16 UTC,
kt,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
// you can also use imports, for example:
// import kotlin.math.*
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
val matrixSize = 3
val listRows = { list: IntArray -> list.asList().chunked(matrixSize) }
val listCols = { list: IntArray ->
sequence {
for (i in 0 until matrixSize) {
for (j in 0 until matrixSize) {
yield(list[j * matrixSize + i])
}
}
}.chunked(matrixSize).toList()
}
fun solution(input: IntArray): IntArray {
val rowSums = listRows(input).map { it.sum() }.toIntArray()
val colSums = listCols(input).map { it.sum() }.toIntArray()
val maxSum = intArrayOf(rowSums.max()!!, colSums.max()!!).maxOrNull()!!
val targetTotal = maxSum * matrixSize
var currentTotal = input.sum()
// while not very functional, I can at least make the function pure ¯\_(ツ)_/¯
val modifiedMatrix = input.clone()
while (currentTotal < targetTotal) {
for (i in 0 until matrixSize) {
if (rowSums[i] == maxSum) {
continue
}
for (j in 0 until matrixSize) {
if (colSums[j] == maxSum) {
continue
}
val increment = min(maxSum - rowSums[i], maxSum - colSums[j])
// mutations coming right up:
modifiedMatrix[(i * matrixSize) + j] += increment
rowSums[i] += increment
colSums[j] += increment
currentTotal += increment
break
}
}
}
return modifiedMatrix
}
solution2(testData2).asList()
Code: 12:13:25 UTC,
kt,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
// you can also use imports, for example:
// import kotlin.math.*
import java.lang.Integer.min
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
val matrixSize = 3
val listRows = { list: IntArray -> list.asList().chunked(matrixSize) }
val listCols = { list: IntArray ->
sequence {
for (i in 0 until matrixSize) {
for (j in 0 until matrixSize) {
yield(list[j * matrixSize + i])
}
}
}.chunked(matrixSize).toList()
}
fun solution(input: IntArray): IntArray {
val rowSums = listRows(input).map { it.sum() }.toIntArray()
val colSums = listCols(input).map { it.sum() }.toIntArray()
val maxSum = intArrayOf(rowSums.max()!!, colSums.max()!!).maxOrNull()!!
val targetTotal = maxSum * matrixSize
var currentTotal = input.sum()
// while not very functional, I can at least make the function pure ¯\_(ツ)_/¯
val modifiedMatrix = input.clone()
while (currentTotal < targetTotal) {
for (i in 0 until matrixSize) {
if (rowSums[i] == maxSum) {
continue
}
for (j in 0 until matrixSize) {
if (colSums[j] == maxSum) {
continue
}
val increment = min(maxSum - rowSums[i], maxSum - colSums[j])
// mutations coming right up:
modifiedMatrix[(i * matrixSize) + j] += increment
rowSums[i] += increment
colSums[j] += increment
currentTotal += increment
break
}
}
}
return modifiedMatrix
}
Analysis
Compile error
solution.kt:23:63: error: unresolved reference: maxOrNull
val maxSum = intArrayOf(rowSums.max()!!, colSums.max()!!).maxOrNull()!!
^
Code: 12:13:43 UTC,
kt,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
// you can also use imports, for example:
// import kotlin.math.*
import java.lang.Integer.min
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
val matrixSize = 3
val listRows = { list: IntArray -> list.asList().chunked(matrixSize) }
val listCols = { list: IntArray ->
sequence {
for (i in 0 until matrixSize) {
for (j in 0 until matrixSize) {
yield(list[j * matrixSize + i])
}
}
}.chunked(matrixSize).toList()
}
fun solution(input: IntArray): IntArray {
val rowSums = listRows(input).map { it.sum() }.toIntArray()
val colSums = listCols(input).map { it.sum() }.toIntArray()
val maxSum = intArrayOf(rowSums.max()!!, colSums.max()!!).max()!!
val targetTotal = maxSum * matrixSize
var currentTotal = input.sum()
// while not very functional, I can at least make the function pure ¯\_(ツ)_/¯
val modifiedMatrix = input.clone()
while (currentTotal < targetTotal) {
for (i in 0 until matrixSize) {
if (rowSums[i] == maxSum) {
continue
}
for (j in 0 until matrixSize) {
if (colSums[j] == maxSum) {
continue
}
val increment = min(maxSum - rowSums[i], maxSum - colSums[j])
// mutations coming right up:
modifiedMatrix[(i * matrixSize) + j] += increment
rowSums[i] += increment
colSums[j] += increment
currentTotal += increment
break
}
}
}
return modifiedMatrix
}
Code: 12:14:11 UTC,
kt,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can also use imports, for example:
// import kotlin.math.*
import java.lang.Integer.min
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
val matrixSize = 3
val listRows = { list: IntArray -> list.asList().chunked(matrixSize) }
val listCols = { list: IntArray ->
sequence {
for (i in 0 until matrixSize) {
for (j in 0 until matrixSize) {
yield(list[j * matrixSize + i])
}
}
}.chunked(matrixSize).toList()
}
fun solution(input: IntArray): IntArray {
val rowSums = listRows(input).map { it.sum() }.toIntArray()
val colSums = listCols(input).map { it.sum() }.toIntArray()
val maxSum = intArrayOf(rowSums.max()!!, colSums.max()!!).max()!!
val targetTotal = maxSum * matrixSize
var currentTotal = input.sum()
// while not very functional, I can at least make the function pure ¯\_(ツ)_/¯
val modifiedMatrix = input.clone()
while (currentTotal < targetTotal) {
for (i in 0 until matrixSize) {
if (rowSums[i] == maxSum) {
continue
}
for (j in 0 until matrixSize) {
if (colSums[j] == maxSum) {
continue
}
// the maximum safe increment is the minimum difference between target/actual row/col sum
val increment = min(maxSum - rowSums[i], maxSum - colSums[j])
// mutations coming right up:
modifiedMatrix[(i * matrixSize) + j] += increment
rowSums[i] += increment
colSums[j] += increment
currentTotal += increment
break
}
}
}
return modifiedMatrix
}
Analysis
Code: 12:14:46 UTC,
kt,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can also use imports, for example:
// import kotlin.math.*
import java.lang.Integer.min
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
val matrixSize = 3
val listRows = { list: IntArray -> list.asList().chunked(matrixSize) }
val listCols = { list: IntArray ->
sequence {
for (i in 0 until matrixSize) {
for (j in 0 until matrixSize) {
yield(list[j * matrixSize + i])
}
}
}.chunked(matrixSize).toList()
}
fun solution(input: IntArray): IntArray {
val rowSums = listRows(input).map { it.sum() }.toIntArray()
val colSums = listCols(input).map { it.sum() }.toIntArray()
val maxSum = intArrayOf(rowSums.max()!!, colSums.max()!!).max()!!
val targetTotal = maxSum * matrixSize
var currentTotal = input.sum()
// while not very functional, I can at least make the function pure ¯\_(ツ)_/¯
val modifiedMatrix = input.clone()
while (currentTotal < targetTotal) {
for (i in 0 until matrixSize) {
if (rowSums[i] == maxSum) {
continue
}
for (j in 0 until matrixSize) {
if (colSums[j] == maxSum) {
continue
}
// the maximum safe increment is the minimum difference between target/actual row/col sum
val increment = min(maxSum - rowSums[i], maxSum - colSums[j])
// mutations coming right up:
modifiedMatrix[(i * matrixSize) + j] += increment
rowSums[i] += increment
colSums[j] += increment
currentTotal += increment
break
}
}
}
return modifiedMatrix
}
Analysis
Code: 12:14:56 UTC,
kt,
final,
score:
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can also use imports, for example:
// import kotlin.math.*
import java.lang.Integer.min
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
val matrixSize = 3
val listRows = { list: IntArray -> list.asList().chunked(matrixSize) }
val listCols = { list: IntArray ->
sequence {
for (i in 0 until matrixSize) {
for (j in 0 until matrixSize) {
yield(list[j * matrixSize + i])
}
}
}.chunked(matrixSize).toList()
}
fun solution(input: IntArray): IntArray {
val rowSums = listRows(input).map { it.sum() }.toIntArray()
val colSums = listCols(input).map { it.sum() }.toIntArray()
val maxSum = intArrayOf(rowSums.max()!!, colSums.max()!!).max()!!
val targetTotal = maxSum * matrixSize
var currentTotal = input.sum()
// while not very functional, I can at least make the function pure ¯\_(ツ)_/¯
val modifiedMatrix = input.clone()
while (currentTotal < targetTotal) {
for (i in 0 until matrixSize) {
if (rowSums[i] == maxSum) {
continue
}
for (j in 0 until matrixSize) {
if (colSums[j] == maxSum) {
continue
}
// the maximum safe increment is the minimum difference between target/actual row/col sum
val increment = min(maxSum - rowSums[i], maxSum - colSums[j])
// mutations coming right up:
modifiedMatrix[(i * matrixSize) + j] += increment
rowSums[i] += increment
colSums[j] += increment
currentTotal += increment
break
}
}
}
return modifiedMatrix
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(1)
expand all
Correctness tests
1.
0.092 s
OK
2.
0.092 s
OK
3.
0.092 s
OK
4.
0.092 s
OK
1.
0.092 s
OK
2.
0.092 s
OK
3.
0.092 s
OK
4.
0.092 s
OK
1.
0.092 s
OK
2.
0.092 s
OK
3.
0.092 s
OK
4.
0.092 s
OK
1.
0.092 s
OK
2.
0.092 s
OK
3.
0.092 s
OK
4.
0.092 s
OK
1.
0.092 s
OK
2.
0.092 s
OK
3.
0.092 s
OK
4.
0.092 s
OK
expand all
Correctness/performance tests
1.
0.092 s
OK
2.
0.092 s
OK
3.
0.092 s
OK
4.
0.092 s
OK
1.
0.092 s
OK
2.
0.092 s
OK
3.
0.092 s
OK
4.
0.092 s
OK
5.
0.092 s
OK
expand all
Performance tests
1.
0.092 s
OK
2.
0.092 s
OK
3.
0.092 s
OK
4.
0.092 s
OK
5.
0.092 s
OK
6.
0.096 s
OK
7.
0.092 s
OK
8.
0.092 s
OK
random_medium_range_zeros
Random matrices with medium value range, max - min <= 2000, and two zeros.
Random matrices with medium value range, max - min <= 2000, and two zeros.
✔
OK
1.
0.092 s
OK
2.
0.092 s
OK
3.
0.092 s
OK
4.
0.092 s
OK
5.
0.092 s
OK
6.
0.092 s
OK
7.
0.092 s
OK
8.
0.092 s
OK
1.
0.092 s
OK
2.
0.092 s
OK
3.
0.092 s
OK
1.
0.092 s
OK
2.
0.092 s
OK
3.
0.092 s
OK
4.
0.092 s
OK
5.
0.092 s
OK
6.
0.092 s
OK
7.
0.088 s
OK
8.
0.092 s
OK