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.
1#include <vector>
2#include <algorithm>
3#include <iostream>
4using namespace std;
5
6bool isMagicSquare(const vector<vector<int>>& grid, int row, int col) {
7 vector<int> nums;
8 for (int i = row; i < row + 3; ++i) {
9 for (int j = col; j < col + 3; ++j) {
10 nums.push_back(grid[i][j]);
11 }
12 }
13 sort(nums.begin(), nums.end());
14 if (nums != vector<int>({1, 2, 3, 4, 5, 6, 7, 8, 9})) return false;
15 int target = grid[row][col] + grid[row][col+1] + grid[row][col+2];
16 for (int i = 0; i < 3; ++i) {
17 if (grid[row+i][col] + grid[row+i][col+1] + grid[row+i][col+2] != target ||
18 grid[row][col+i] + grid[row+1][col+i] + grid[row+2][col+i] != target)
19 return false;
20 }
21 return (grid[row][col] + grid[row+1][col+1] + grid[row+2][col+2] == target &&
22 grid[row][col+2] + grid[row+1][col+1] + grid[row+2][col] == target);
23}
24
25int numMagicSquaresInside(vector<vector<int>>& grid) {
26 int count = 0;
27 for (int i = 0; i <= grid.size() - 3; ++i) {
28 for (int j = 0; j <= grid[0].size() - 3; ++j) {
29 if (isMagicSquare(grid, i, j)) ++count;
30 }
31 }
32 return count;
33}
34
35int main() {
36 vector<vector<int>> grid = {{4,3,8,4},{9,5,1,9},{2,7,6,2}};
37 cout << numMagicSquaresInside(grid); // Output: 1
38 return 0;
39}This C++ solution creates a helper function to verify if a given 3x3 subgrid is a magic square. It checks the number range, distinctiveness, and sums equality. The main function iterates over every possible subgrid and counts the valid 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.