Sponsored
Sponsored
This approach involves iterating through each possible 3x3 subgrid within the larger grid. For each subgrid, we check if it is a magic square by validating the sum of each row, each column, and both diagonals to see if they all equal 15. Additionally, check if the subgrid contains all distinct numbers between 1 and 9. This straightforward method works well given the constraint where the largest grid size is 10x10.
Time complexity: O(n*m), where n and m are the number of rows and columns, respectively, since we check each 3x3 subgrid.
Space complexity: O(1), no extra space is required other than a few variables.
1def is_magic_square(grid, row, col):
2 nums = [grid[row+i][col+j] for i in range(3) for j in range(3)]
3 if sorted(nums) != list(range(1, 10)):
4 return False
5 return (sum(grid[row][col:col+3]) ==
6 sum(grid[row+1][col:col+3]) ==
7 sum(grid[row+2][col:col+3]) ==
8 sum(grid[row+i][col] for i in range(3)) ==
9 sum(grid[row+i][col+1] for i in range(3)) ==
10 sum(grid[row+i][col+2] for i in range(3)) ==
11 grid[row][col] + grid[row+1][col+1] + grid[row+2][col+2] ==
12 grid[row][col+2] + grid[row+1][col+1] + grid[row+2][col])
13
14def num_magic_squares_inside(grid):
15 count = 0
16 for i in range(len(grid) - 2):
17 for j in range(len(grid[0]) - 2):
18 if is_magic_square(grid, i, j):
19 count += 1
20 return count
21
22grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]]
23print(num_magic_squares_inside(grid)) # Output: 1This Python function first checks if the numbers in the 3x3 subgrid are exactly those between 1 and 9. If they are, it further checks if the sums of all rows, columns, and diagonals are equal to 15. The main function iterates over all possible subgrids within the main grid and counts how many are magic squares.
This approach leverages the fact that any 3x3 magic square with numbers from 1 to 9 must have specific sums for rows, columns, and diagonals. By using pattern matching, we can check if the middle element is always 5 (since the sum of 1 to 9 is 45, and any 3 rows, columns, or diagonals equate to the central element being crucial with 15/3 = 5). This limits the checks needed and optimizes the process.
Time complexity: O(n*m), since each subgrid must be checked.
Space complexity: O(1), since memory use is constant beyond some numeric vectors.
1import java.util.HashSet;
2
In this Java approach, a Set is used to collect numbers in the subgrid to check uniqueness and if they contain numbers between 1 and 9 only. The pivotal grid checking is simplified by pattern checks as previously mentioned, making the checks concise and optimized.