img

Software Development Blog

Back

Magic Square HackerRank Exercise

Problem

Defined a magic square n x n to be a matrix of distinct positive integers from 1 to n^2 where the sum of any row, column, or diagonal of length n is always equal to the same number: the magic constant. The given 3 x 3 a matrix s of integers in the inclusive range [1, 9]. The program can convert any digit a to any other digit b in the range [1, 9] at cost of [a - b]. Given s, convert it into a magic square at a minimal cost. Print this cost on a new line.

Solving

The solving of this exercise isn't so difficult. The main issue here is to understand the meaning and specification. I want to define the main parts of the magic square:

  • All rows, columns, diagonals are always equal to n^2, where n is a matrix size. (Matrix should be a square)
  • Items should be the arithmetic progression. Matrix with all number 3 or 4 for example is not a magic square. (It can be helpful if you need to calculate the sum of all items in a huge magic square). So the magic square 3 x 3 should contain only n ^ 2 = 1, 2, 3, 4, 5, 6, 7, 8, 9
  • The order has matter!

So, in this exercise, we have only a 3 x 3 matrix. Magic square like that has only 8 possible variations of order. We need to compare this matrix with all these variations. The solving can be smarter for n x n matrix. But it was so slow (exercises on HackerRank has time complexity limitations, and that's why solving looks silly).

We need to create all possible variations of the magic square with 3 x 3 size. Then calculate the difference between each variation and input matrix. The minimum value of these differences is our answer

My Social Media

LinkedIn Twitter Original Blog Github HackerRank

Photo by Blake Connally on Unsplash

Recent Posts

What are UUID identifiers in Swift?

READ MORE

How to use Comparable protocol

READ MORE