We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Your link will only ever open to the code of the person who clicked it.
Regardless of that, you must have a math error if you're getting lower costs than the expected minimum costs.
Filling out a magic square is an O(n^2) problem, where n is the number of elements in a single row or column. There are three different types of magic square (n is odd, n is even and divisible by 4, n is even and not divisible by 4) and each type has a different algorithm for solving it. As we are only dealing with an odd-numbered 3 by 3 magic square, it can be solved using the "up and right" method.
The up and right method is as follows:
1. Starting from a cardinal position at the edge (IE directly horizontal or vertical from the center), place the first number;
2. Move up one and right one;
3. If moving up places you outside the square, wrap to the bottom;
4. If moving right places you outside the square, wrap to the left;
5. If the position already has a number, move left one, down two;
6. Wrap as necessary so that you remain inside the square;
7. Increment the number and place it;
8. Repeat moving and placing until all positions are filled.
Up is defined as the direction taken to move from the center position to the starting position, while right is defined as orthagonal to up. Note that this means "moving right" can actually be "moving left."
Because both right and left work, and there are four possible directions that can be defined as "up," every odd-numbered magic square has 8 possible valid solutions.
With all this, you can solve the problem successfully. There are two main ways to solve this, an easy way and a memory-efficient way.
The easy way is to create, either by raw data inputs or programmatically, all 8 valid magic squares and then compare the input against them, taking the smallest absolute difference as your answer. This takes O(8n^2) memory space to do.
The memory-efficient way is to "walk" the square 8 times using the "up and right" method, starting from the position the 1 would be. This takes O(1) memory space to do, and can in fact take less steps than the easy way, though it still has the same number of steps required in the worst case.
Both ways of solving the problem will arrive at the same answer.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Forming a Magic Square
You are viewing a single comment's thread. Return to all comments →
Your link will only ever open to the code of the person who clicked it.
Regardless of that, you must have a math error if you're getting lower costs than the expected minimum costs.
Filling out a magic square is an O(n^2) problem, where n is the number of elements in a single row or column. There are three different types of magic square (n is odd, n is even and divisible by 4, n is even and not divisible by 4) and each type has a different algorithm for solving it. As we are only dealing with an odd-numbered 3 by 3 magic square, it can be solved using the "up and right" method.
The up and right method is as follows: 1. Starting from a cardinal position at the edge (IE directly horizontal or vertical from the center), place the first number; 2. Move up one and right one; 3. If moving up places you outside the square, wrap to the bottom; 4. If moving right places you outside the square, wrap to the left; 5. If the position already has a number, move left one, down two; 6. Wrap as necessary so that you remain inside the square; 7. Increment the number and place it; 8. Repeat moving and placing until all positions are filled.
Up is defined as the direction taken to move from the center position to the starting position, while right is defined as orthagonal to up. Note that this means "moving right" can actually be "moving left."
Because both right and left work, and there are four possible directions that can be defined as "up," every odd-numbered magic square has 8 possible valid solutions.
With all this, you can solve the problem successfully. There are two main ways to solve this, an easy way and a memory-efficient way.
The easy way is to create, either by raw data inputs or programmatically, all 8 valid magic squares and then compare the input against them, taking the smallest absolute difference as your answer. This takes O(8n^2) memory space to do.
The memory-efficient way is to "walk" the square 8 times using the "up and right" method, starting from the position the 1 would be. This takes O(1) memory space to do, and can in fact take less steps than the easy way, though it still has the same number of steps required in the worst case.
Both ways of solving the problem will arrive at the same answer.