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:
function solution(A);
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 JavaScript
Time spent on task 5 minutes
Notes
not defined yet
Code: 08:52:34 UTC,
java,
autosave
Code: 08:57:17 UTC,
js,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
let getSum = (arr) => {
return arr.reduce((acc, val) => {
return acc + val;
}, 0);
};
let findMaxSum = (data) => {
let max = 0;
for (let i = 0; i < data.length; i++) {
let thisSum = getSum(data[i]);
if (thisSum > max) {
max = thisSum;
}
}
return max;
};
let analyzeCollection = (data, MAX) => {
let minIndex = 0;
// max possible sum
let min = 3 * 100000000;
let tracker = [];
for (let i = 0; i < data.length; i++) {
let thisSum = getSum(data[i]);
tracker.push(thisSum);
if (thisSum <= min) {
min = thisSum;
minIndex = i;
}
}
const isSame = tracker[0] === tracker[1] && tracker[1] === tracker[2];
tracker.sort((a, b) => a - b);
return {
min,
minIndex,
isSame,
minDiff: tracker[1] - tracker[0] || tracker[2] - tracker[1] || MAX - tracker[0]
};
};
let organizeArray = (data) => {
// by far the fastest way to organize rows/cols
return {
rows: [
[data[0], data[1], data[2]],
[data[3], data[4], data[5]],
[data[6], data[7], data[8]]
],
cols: [
[data[0], data[3], data[6]],
[data[1], data[4], data[7]],
[data[2], data[5], data[8]]
]
};
};
function getBestNumToIncrease(rows, cols, MAX) {
// best number to increase => benti
// find lowest row sum and col sum
// best number to increase is the intersection of those two collections
let { minIndex: minRowIndex, isSame: rowsSame, minDiff: minDiffRow } = analyzeCollection(rows, MAX);
let { minIndex: minColIndex, isSame: colsSame, minDiff: minDiffCol } = analyzeCollection(cols, MAX);
// calculate largest safest increment for benti
return [minRowIndex, minColIndex, rowsSame && colsSame, Math.min(minDiffRow, minDiffCol)];
}
function solveData([rows, cols], MAX) {
let [r_benti, c_benti, isSolved, minimalIncrement] = getBestNumToIncrease(rows, cols, MAX);
if (isSolved) {
return [...rows[0], ...rows[1], ...rows[2]];
}
rows[r_benti][c_benti] += minimalIncrement;
cols[c_benti][r_benti] += minimalIncrement;
return solveData([rows, cols], MAX);
}
let solution = (A) => {
let { rows, cols } = organizeArray(A);
let SUMS = [...rows, ...cols].map(getSum);
let MAX = Math.max(...SUMS);
return solveData([rows, cols], MAX);
};
Code: 08:57:17 UTC,
js,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
let getSum = (arr) => {
return arr.reduce((acc, val) => {
return acc + val;
}, 0);
};
let findMaxSum = (data) => {
let max = 0;
for (let i = 0; i < data.length; i++) {
let thisSum = getSum(data[i]);
if (thisSum > max) {
max = thisSum;
}
}
return max;
};
let analyzeCollection = (data, MAX) => {
let minIndex = 0;
// max possible sum
let min = 3 * 100000000;
let tracker = [];
for (let i = 0; i < data.length; i++) {
let thisSum = getSum(data[i]);
tracker.push(thisSum);
if (thisSum <= min) {
min = thisSum;
minIndex = i;
}
}
const isSame = tracker[0] === tracker[1] && tracker[1] === tracker[2];
tracker.sort((a, b) => a - b);
return {
min,
minIndex,
isSame,
minDiff: tracker[1] - tracker[0] || tracker[2] - tracker[1] || MAX - tracker[0]
};
};
let organizeArray = (data) => {
// by far the fastest way to organize rows/cols
return {
rows: [
[data[0], data[1], data[2]],
[data[3], data[4], data[5]],
[data[6], data[7], data[8]]
],
cols: [
[data[0], data[3], data[6]],
[data[1], data[4], data[7]],
[data[2], data[5], data[8]]
]
};
};
function getBestNumToIncrease(rows, cols, MAX) {
// best number to increase => benti
// find lowest row sum and col sum
// best number to increase is the intersection of those two collections
let { minIndex: minRowIndex, isSame: rowsSame, minDiff: minDiffRow } = analyzeCollection(rows, MAX);
let { minIndex: minColIndex, isSame: colsSame, minDiff: minDiffCol } = analyzeCollection(cols, MAX);
// calculate largest safest increment for benti
return [minRowIndex, minColIndex, rowsSame && colsSame, Math.min(minDiffRow, minDiffCol)];
}
function solveData([rows, cols], MAX) {
let [r_benti, c_benti, isSolved, minimalIncrement] = getBestNumToIncrease(rows, cols, MAX);
if (isSolved) {
return [...rows[0], ...rows[1], ...rows[2]];
}
rows[r_benti][c_benti] += minimalIncrement;
cols[c_benti][r_benti] += minimalIncrement;
return solveData([rows, cols], MAX);
}
let solution = (A) => {
let { rows, cols } = organizeArray(A);
let SUMS = [...rows, ...cols].map(getSum);
let MAX = Math.max(...SUMS);
return solveData([rows, cols], MAX);
};
Analysis
Code: 08:57:20 UTC,
js,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
let getSum = (arr) => {
return arr.reduce((acc, val) => {
return acc + val;
}, 0);
};
let findMaxSum = (data) => {
let max = 0;
for (let i = 0; i < data.length; i++) {
let thisSum = getSum(data[i]);
if (thisSum > max) {
max = thisSum;
}
}
return max;
};
let analyzeCollection = (data, MAX) => {
let minIndex = 0;
// max possible sum
let min = 3 * 100000000;
let tracker = [];
for (let i = 0; i < data.length; i++) {
let thisSum = getSum(data[i]);
tracker.push(thisSum);
if (thisSum <= min) {
min = thisSum;
minIndex = i;
}
}
const isSame = tracker[0] === tracker[1] && tracker[1] === tracker[2];
tracker.sort((a, b) => a - b);
return {
min,
minIndex,
isSame,
minDiff: tracker[1] - tracker[0] || tracker[2] - tracker[1] || MAX - tracker[0]
};
};
let organizeArray = (data) => {
// by far the fastest way to organize rows/cols
return {
rows: [
[data[0], data[1], data[2]],
[data[3], data[4], data[5]],
[data[6], data[7], data[8]]
],
cols: [
[data[0], data[3], data[6]],
[data[1], data[4], data[7]],
[data[2], data[5], data[8]]
]
};
};
function getBestNumToIncrease(rows, cols, MAX) {
// best number to increase => benti
// find lowest row sum and col sum
// best number to increase is the intersection of those two collections
let { minIndex: minRowIndex, isSame: rowsSame, minDiff: minDiffRow } = analyzeCollection(rows, MAX);
let { minIndex: minColIndex, isSame: colsSame, minDiff: minDiffCol } = analyzeCollection(cols, MAX);
// calculate largest safest increment for benti
return [minRowIndex, minColIndex, rowsSame && colsSame, Math.min(minDiffRow, minDiffCol)];
}
function solveData([rows, cols], MAX) {
let [r_benti, c_benti, isSolved, minimalIncrement] = getBestNumToIncrease(rows, cols, MAX);
if (isSolved) {
return [...rows[0], ...rows[1], ...rows[2]];
}
rows[r_benti][c_benti] += minimalIncrement;
cols[c_benti][r_benti] += minimalIncrement;
return solveData([rows, cols], MAX);
}
let solution = (A) => {
let { rows, cols } = organizeArray(A);
let SUMS = [...rows, ...cols].map(getSum);
let MAX = Math.max(...SUMS);
return solveData([rows, cols], MAX);
};
Analysis
Code: 08:57:24 UTC,
js,
final,
score:
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
let getSum = (arr) => {
return arr.reduce((acc, val) => {
return acc + val;
}, 0);
};
let findMaxSum = (data) => {
let max = 0;
for (let i = 0; i < data.length; i++) {
let thisSum = getSum(data[i]);
if (thisSum > max) {
max = thisSum;
}
}
return max;
};
let analyzeCollection = (data, MAX) => {
let minIndex = 0;
// max possible sum
let min = 3 * 100000000;
let tracker = [];
for (let i = 0; i < data.length; i++) {
let thisSum = getSum(data[i]);
tracker.push(thisSum);
if (thisSum <= min) {
min = thisSum;
minIndex = i;
}
}
const isSame = tracker[0] === tracker[1] && tracker[1] === tracker[2];
tracker.sort((a, b) => a - b);
return {
min,
minIndex,
isSame,
minDiff: tracker[1] - tracker[0] || tracker[2] - tracker[1] || MAX - tracker[0]
};
};
let organizeArray = (data) => {
// by far the fastest way to organize rows/cols
return {
rows: [
[data[0], data[1], data[2]],
[data[3], data[4], data[5]],
[data[6], data[7], data[8]]
],
cols: [
[data[0], data[3], data[6]],
[data[1], data[4], data[7]],
[data[2], data[5], data[8]]
]
};
};
function getBestNumToIncrease(rows, cols, MAX) {
// best number to increase => benti
// find lowest row sum and col sum
// best number to increase is the intersection of those two collections
let { minIndex: minRowIndex, isSame: rowsSame, minDiff: minDiffRow } = analyzeCollection(rows, MAX);
let { minIndex: minColIndex, isSame: colsSame, minDiff: minDiffCol } = analyzeCollection(cols, MAX);
// calculate largest safest increment for benti
return [minRowIndex, minColIndex, rowsSame && colsSame, Math.min(minDiffRow, minDiffCol)];
}
function solveData([rows, cols], MAX) {
let [r_benti, c_benti, isSolved, minimalIncrement] = getBestNumToIncrease(rows, cols, MAX);
if (isSolved) {
return [...rows[0], ...rows[1], ...rows[2]];
}
rows[r_benti][c_benti] += minimalIncrement;
cols[c_benti][r_benti] += minimalIncrement;
return solveData([rows, cols], MAX);
}
let solution = (A) => {
let { rows, cols } = organizeArray(A);
let SUMS = [...rows, ...cols].map(getSum);
let MAX = Math.max(...SUMS);
return solveData([rows, cols], MAX);
};
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(1)
expand all
Correctness tests
1.
0.072 s
OK
2.
0.072 s
OK
3.
0.072 s
OK
4.
0.072 s
OK
1.
0.076 s
OK
2.
0.072 s
OK
3.
0.072 s
OK
4.
0.072 s
OK
1.
0.072 s
OK
2.
0.072 s
OK
3.
0.072 s
OK
4.
0.072 s
OK
1.
0.072 s
OK
2.
0.072 s
OK
3.
0.072 s
OK
4.
0.072 s
OK
1.
0.072 s
OK
2.
0.072 s
OK
3.
0.072 s
OK
4.
0.072 s
OK
expand all
Correctness/performance tests
1.
0.072 s
OK
2.
0.072 s
OK
3.
0.072 s
OK
4.
0.072 s
OK
1.
0.076 s
OK
2.
0.072 s
OK
3.
0.072 s
OK
4.
0.072 s
OK
5.
0.072 s
OK
expand all
Performance tests
1.
0.072 s
OK
2.
0.072 s
OK
3.
0.072 s
OK
4.
0.072 s
OK
5.
0.072 s
OK
6.
0.072 s
OK
7.
0.072 s
OK
8.
0.072 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.072 s
OK
2.
0.072 s
OK
3.
0.076 s
OK
4.
0.072 s
OK
5.
0.072 s
OK
6.
0.072 s
OK
7.
0.072 s
OK
8.
0.072 s
OK
1.
0.072 s
OK
2.
0.072 s
OK
3.
0.072 s
OK
1.
0.072 s
OK
2.
0.072 s
OK
3.
0.072 s
OK
4.
0.072 s
OK
5.
0.072 s
OK
6.
0.072 s
OK
7.
0.072 s
OK
8.
0.072 s
OK