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:
class Solution { public int[] solution(int[] 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 Java 21
Time spent on task 40 minutes
Notes
not defined yet
Code: 08:51:32 UTC,
java,
autosave
Code: 09:23:18 UTC,
java,
autosave
Code: 09:23:48 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] A) {
// write your code in Java SE 8
int max = 0;
for(int i = 0; i < 3; i++){
int sum = 0;
for(int j = 0; j < 3; j++){
int index = i*3 + j;
}
}
return A;
}
}
Code: 09:23:59 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] A) {
// write your code in Java SE 8
int max = 0;
for(int i = 0; i < 3; i++){
int sum = 0;
for(int j = 0; j < 3; j++){
int index = i*3 + j;
sum +=
}
}
return A;
}
}
Code: 09:24:20 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] data) {
// write your code in Java SE 8
int max = 0;
for(int i = 0; i < 3; i++){
int sum = 0;
for(int j = 0; j < 3; j++){
int index = i*3 + j;
sum += data[index];
}
max = Integer.max(max, sum);
}
return data;
}
}
Code: 09:24:51 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] data) {
// write your code in Java SE 8
int max = 0;
int[]row = new int[3];
int[]col = new int[3];
for(int i = 0; i < 3; i++){
int sum = 0;
for(int j = 0; j < 3; j++){
int index = i*3 + j;
sum += data[index];
}
row[i] = sum;
max = Integer.max(max, sum);
}
for(int )
return data;
}
}
Code: 09:25:08 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] data) {
// write your code in Java SE 8
int max = 0;
int[]row = new int[3];
int[]col = new int[3];
for(int i = 0; i < 3; i++){
int sum = 0;
for(int j = 0; j < 3; j++){
int index = i*3 + j;
sum += data[index];
}
row[i] = sum;
max = Integer.max(max, sum);
}
for(int j = 0; j < 3; j++){
int sum = 0;
for(int i = 0; i < 3; i++){
}
}
return data;
}
}
Code: 09:25:30 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] data) {
// write your code in Java SE 8
int max = 0;
int[]row = new int[3];
int[]col = new int[3];
for(int i = 0; i < 3; i++){
int sum = 0;
for(int j = 0; j < 3; j++){
int index = i*3 + j;
sum += data[index];
}
row[i] = sum;
max = Integer.max(max, sum);
}
for(int j = 0; j < 3; j++){
int sum = 0;
for(int i = 0; i < 3; i++){
int index = i*3 + j;
sum += data[index];
}
col[j] = sum;
max = Integer.max(max, sum);
}
return data;
}
}
Code: 09:29:54 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] data) {
// write your code in Java SE 8
int max = 0;
int[]row = new int[3];
int[]col = new int[3];
for(int i = 0; i < 3; i++){
int sum = 0;
for(int j = 0; j < 3; j++){
int index = i*3 + j;
sum += data[index];
}
row[i] = sum;
max = Integer.max(max, sum);
}
for(int j = 0; j < 3; j++){
int sum = 0;
for(int i = 0; i < 3; i++){
int index = i*3 + j;
sum += data[index];
}
col[j] = sum;
max = Integer.max(max, sum);
}
for(int )
return data;
}
}
Code: 09:30:09 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] data) {
// write your code in Java SE 8
int max = 0;
int[]row = new int[3];
int[]col = new int[3];
for(int i = 0; i < 3; i++){
int sum = 0;
for(int j = 0; j < 3; j++){
int index = i*3 + j;
sum += data[index];
}
row[i] = sum;
max = Integer.max(max, sum);
}
for(int j = 0; j < 3; j++){
int sum = 0;
for(int i = 0; i < 3; i++){
int index = i*3 + j;
sum += data[index];
}
col[j] = sum;
max = Integer.max(max, sum);
}
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
}
}
return data;
}
}
Code: 09:30:26 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] data) {
// write your code in Java SE 8
int max = 0;
int[]row = new int[3];
int[]col = new int[3];
for(int i = 0; i < 3; i++){
int sum = 0;
for(int j = 0; j < 3; j++){
int index = i*3 + j;
sum += data[index];
}
row[i] = sum;
max = Integer.max(max, sum);
}
for(int j = 0; j < 3; j++){
int sum = 0;
for(int i = 0; i < 3; i++){
int index = i*3 + j;
sum += data[index];
}
col[j] = sum;
max = Integer.max(max, sum);
}
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
int need = max - row[i]
}
}
return data;
}
}
Code: 09:30:42 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] data) {
// write your code in Java SE 8
int max = 0;
int[]row = new int[3];
int[]col = new int[3];
for(int i = 0; i < 3; i++){
int sum = 0;
for(int j = 0; j < 3; j++){
int index = i*3 + j;
sum += data[index];
}
row[i] = sum;
max = Integer.max(max, sum);
}
for(int j = 0; j < 3; j++){
int sum = 0;
for(int i = 0; i < 3; i++){
int index = i*3 + j;
sum += data[index];
}
col[j] = sum;
max = Integer.max(max, sum);
}
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
int need = Integer.min(max - row[i], max - col[j]);
}
}
return data;
}
}
Code: 09:30:59 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] data) {
// write your code in Java SE 8
int max = 0;
int[]row = new int[3];
int[]col = new int[3];
for(int i = 0; i < 3; i++){
int sum = 0;
for(int j = 0; j < 3; j++){
int index = i*3 + j;
sum += data[index];
}
row[i] = sum;
max = Integer.max(max, sum);
}
for(int j = 0; j < 3; j++){
int sum = 0;
for(int i = 0; i < 3; i++){
int index = i*3 + j;
sum += data[index];
}
col[j] = sum;
max = Integer.max(max, sum);
}
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
int need = Integer.min(max - row[i], max - col[j]);
data[i*3 + j] += need;
row[i] += need;
col[j] += need;
}
}
return data;
}
}
Code: 09:31:00 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] data) {
// write your code in Java SE 8
int max = 0;
int[]row = new int[3];
int[]col = new int[3];
for(int i = 0; i < 3; i++){
int sum = 0;
for(int j = 0; j < 3; j++){
int index = i*3 + j;
sum += data[index];
}
row[i] = sum;
max = Integer.max(max, sum);
}
for(int j = 0; j < 3; j++){
int sum = 0;
for(int i = 0; i < 3; i++){
int index = i*3 + j;
sum += data[index];
}
col[j] = sum;
max = Integer.max(max, sum);
}
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
int need = Integer.min(max - row[i], max - col[j]);
data[i*3 + j] += need;
row[i] += need;
col[j] += need;
}
}
return data;
}
}
Analysis
Code: 09:31:08 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] data) {
// write your code in Java SE 8
int max = 0;
int[]row = new int[3];
int[]col = new int[3];
for(int i = 0; i < 3; i++){
int sum = 0;
for(int j = 0; j < 3; j++){
int index = i*3 + j;
sum += data[index];
}
row[i] = sum;
max = Integer.max(max, sum);
}
for(int j = 0; j < 3; j++){
int sum = 0;
for(int i = 0; i < 3; i++){
int index = i*3 + j;
sum += data[index];
}
col[j] = sum;
max = Integer.max(max, sum);
}
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
int need = Integer.min(max - row[i], max - col[j]);
data[i*3 + j] += need;
row[i] += need;
col[j] += need;
}
}
return data;
}
}
Analysis
Code: 09:31:13 UTC,
java,
final,
score:
100
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] data) {
// write your code in Java SE 8
int max = 0;
int[]row = new int[3];
int[]col = new int[3];
for(int i = 0; i < 3; i++){
int sum = 0;
for(int j = 0; j < 3; j++){
int index = i*3 + j;
sum += data[index];
}
row[i] = sum;
max = Integer.max(max, sum);
}
for(int j = 0; j < 3; j++){
int sum = 0;
for(int i = 0; i < 3; i++){
int index = i*3 + j;
sum += data[index];
}
col[j] = sum;
max = Integer.max(max, sum);
}
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
int need = Integer.min(max - row[i], max - col[j]);
data[i*3 + j] += need;
row[i] += need;
col[j] += need;
}
}
return data;
}
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(1)
expand all
Correctness tests
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
4.
0.004 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
4.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
4.
0.008 s
OK
1.
0.008 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.004 s
OK
1.
0.008 s
OK
2.
0.004 s
OK
3.
0.008 s
OK
4.
0.004 s
OK
expand all
Correctness/performance tests
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.004 s
OK
5.
0.004 s
OK
expand all
Performance tests
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
5.
0.004 s
OK
6.
0.004 s
OK
7.
0.004 s
OK
8.
0.004 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.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.004 s
OK
5.
0.008 s
OK
6.
0.004 s
OK
7.
0.004 s
OK
8.
0.004 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
1.
0.008 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.008 s
OK
5.
0.008 s
OK
6.
0.008 s
OK
7.
0.004 s
OK
8.
0.004 s
OK