Given a matrix mat[][] of size N x N, the task is to count the number of submatrices with the following properties:
- The sum of all elements in the submatrix is odd.
- The number of elements in the submatrix is odd.
Examples:
Input: mat[][] = {{1, 2, 3}, {7, 5, 9}, {6, 8, 10}}
Output: 8
Explanation: As here total 8 submatrix is available in given matrix in which no. of elements is odd and sum of elements is also odd list of that matrix are {{1}}, {{3}}, {{7}}, {{5}}, {{9}}, {{7, 5, 9}}, {{2}, {5}, {8}}, {{1, 2, 3}, {7, 5, 9}, {5, 9, 6}}Input: mat[][] = {{15, 2, 31}, {17, 11, 12}, {16, 51, 10}, {13, 52, 18}}
Output: 14
Naive Approach: We can solve this problem using a brute force approach, where we consider all possible submatrices of the given matrix and check if they satisfy the given properties.
Below is the code for the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;int oddSumOddElementCountSubmatrix( vector<vector<int> >& mat){ // Size of given 2-D matrix int n = mat.size(); int count = 0; // Here we need all submatrix which // contains odd no. of element in them. // So all the matrix whose size is in // form 1*3, 1*5, 1*7, 3*1, 3*3, 3*5, // 3*7, 5*1, ... are valid submatrix // now we need to check for that sum // of element present in that // submatrix is odd or not // So this nested 4 for loop generates // all submatrix with size as // mentioned above for (int rsize = 1; rsize <= n; rsize += 2) { for (int csize = 1; csize <= n; csize += 2) { for (int row = 0; row + rsize <= n; row++) { for (int col = 0; col + csize <= n; col++) { // Now do summation of // element present in // that subarray and if // it's odd increment // the count int sum = 0; for (int i = row; i < row + rsize; i++) { for (int j = col; j < col + csize; j++) { sum += mat[i][j]; } } if (sum % 2 == 1) { count++; } } } } } // Return answer return count;}// Drivers codeint main(){ vector<vector<int> > mat = { { 1, 2, 3 }, { 7, 5, 9 }, { 6, 8, 10 } }; // Function Call cout << "Number of odd sum submatrices with odd number " "of elements: " << oddSumOddElementCountSubmatrix(mat) << "\n"; return 0;} |
Java
import java.util.*;public class Main { public static int oddSumOddElementCountSubmatrix(int[][] mat) { // Size of given 2-D matrix int n = mat.length; int count = 0; // Here we need all submatrix which // contains odd no. of element in them. // So all the matrix whose size is in // form 1*3, 1*5, 1*7, 3*1, 3*3, 3*5, // 3*7, 5*1, ... are valid submatrix // now we need to check for that sum // of element present in that // submatrix is odd or not // So this nested 4 for loop generates // all submatrix with size as // mentioned above for (int rsize = 1; rsize <= n; rsize += 2) { for (int csize = 1; csize <= n; csize += 2) { for (int row = 0; row + rsize <= n; row++) { for (int col = 0; col + csize <= n; col++) { // Now do summation of // element present in // that subarray and if // it's odd increment // the count int sum = 0; for (int i = row; i < row + rsize; i++) { for (int j = col; j < col + csize; j++) { sum += mat[i][j]; } } if (sum % 2 == 1) { count++; } } } } } // Return answer return count; } // Drivers code public static void main(String[] args) { int[][] mat = { { 1, 2, 3 }, { 7, 5, 9 }, { 6, 8, 10 } }; // Function Call System.out.println("Number of odd sum submatrices with odd number of elements: " + oddSumOddElementCountSubmatrix(mat)); }}//This code is contributed by tushar rokade |
Python3
def oddSumOddElementCountSubmatrix(mat): # Size of given 2-D matrix n = len(mat) count = 0 # Here we need all submatrix which # contains odd no. of element in them. # So all the matrix whose size is in # form 1*3, 1*5, 1*7, 3*1, 3*3, 3*5, # 3*7, 5*1, ... are valid submatrix # now we need to check for that sum # of element present in that # submatrix is odd or not # So this nested 4 for loop generates # all submatrix with size as # mentioned above for rsize in range(1, n+1, 2): for csize in range(1, n+1, 2): for row in range(n-rsize+1): for col in range(n-csize+1): # Now do summation of # element present in # that subarray and if # it's odd increment # the count subMatSum = 0 for i in range(row, row+rsize): for j in range(col, col+csize): subMatSum += mat[i][j] if subMatSum % 2 == 1: count += 1 # Return answer return count# Driver codemat = [[1, 2, 3], [7, 5, 9], [6, 8, 10]]print("Number of odd sum submatrices with odd number of elements: ", oddSumOddElementCountSubmatrix(mat)) |
C#
// C# code for above approachusing System;public class GFG {public static int oddSumOddElementCountSubmatrix(int[][] mat) { // Size of given 2-D matrix int n = mat.Length; int count = 0; // Here we need all submatrix which // contains odd no. of element in them. // So all the matrix whose size is in // form 1*3, 1*5, 1*7, 3*1, 3*3, 3*5, // 3*7, 5*1, ... are valid submatrix // now we need to check for that sum // of element present in that // submatrix is odd or not // So this nested 4 for loop generates // all submatrix with size as // mentioned above for (int rsize = 1; rsize <= n; rsize += 2) { for (int csize = 1; csize <= n; csize += 2) { for (int row = 0; row + rsize <= n; row++) { for (int col = 0; col + csize <= n; col++) { // Now do summation of // element present in // that subarray and if // it's odd increment // the count int sum = 0; for (int i = row; i < row + rsize; i++) { for (int j = col; j < col + csize; j++) { sum += mat[i][j]; } } if (sum % 2 == 1) { count++; } } } } } // Return answer return count;}// Drivers codepublic static void Main() { int[][] mat = new int[][] { new int[] { 1, 2, 3 }, new int[] { 7, 5, 9 }, new int[] { 6, 8, 10 } }; // Function Call Console.WriteLine("Number of odd sum submatrices with odd number of elements: " + oddSumOddElementCountSubmatrix(mat));}}// This code is contributed by Vaibhav Nandan |
Javascript
function oddSumOddElementCountSubmatrix(mat) { // Size of given 2-D matrix let n = mat.length; let count = 0; // Here we need all submatrix which // contains odd no. of element in them. // So all the matrix whose size is in // form 1*3, 1*5, 1*7, 3*1, 3*3, 3*5, // 3*7, 5*1, ... are valid submatrix // now we need to check for that sum // of element present in that // submatrix is odd or not // So this nested 4 for loop generates // all submatrix with size as // mentioned above for (let rsize = 1; rsize <= n; rsize += 2) { for (let csize = 1; csize <= n; csize += 2) { for (let row = 0; row + rsize <= n; row++) { for (let col = 0; col + csize <= n; col++) { // Now do summation of // element present in // that subarray and if // it's odd increment // the count let sum = 0; for (let i = row; i < row + rsize; i++) { for (let j = col; j < col + csize; j++) { sum += mat[i][j]; } } if (sum % 2 === 1) { count++; } } } } } // Return answer return count;}// Test caselet mat = [[1, 2, 3], [7, 5, 9], [6, 8, 10]];console.log("Number of odd sum submatrices with odd number of elements: " + oddSumOddElementCountSubmatrix(mat)); |
Output
Number of odd sum submatrices with odd number of elements: 8
Time Complexity: O(N6), as 6 nested for loop requires to make matrix as required
Auxiliary Space: O(1), no extra space used.
Efficient Approach: To solve the problem follow the below idea:
- To optimize the solution, we can use a technique called prefix sums. We can precompute the sum of all elements in the matrix up to a particular row and column and store it in a separate matrix. This precomputation will allow us to calculate the sum of any submatrix in constant time.
- Once we have precomputed the prefix sums, we can iterate over all possible submatrices and check if they satisfy the above properties. To check if the sum of elements in a submatrix is odd, we can subtract the prefix sum of the bottom-right corner from the prefix sum of the top-left corner. If the difference is odd, the sum of the submatrix is odd.
- To check if the number of elements in a submatrix is odd, we can count the number of rows and columns in the submatrix and check if their product is odd.
Below are the steps for the above approach:
- Initialize a prefix sum matrix with 0, of the same size as the given matrix.
- Precompute the prefix sums of all elements up to each row and column in the prefix sum matrix.
- prefixSum[i][j] = prefixSum[i – 1][j] + prefixSum[i][j – 1] – prefixSum[i – 1][j – 1] + matrix[i – 1][j – 1].
- Iterate over all possible submatrices in the given matrix.
- For each submatrix, calculate the sum of its elements using the prefix sum matrix.
- If the sum is odd, count the number of elements in the submatrix.
- If the number of elements is odd, increment the counter.
- Return the final count.
Below is the code for the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;int countOddSumSubmatrices(vector<vector<int> >& matrix){ int n = matrix.size(); int m = matrix[0].size(); int count = 0; // Initialize prefix sum matrix vector<vector<int> > prefixSum(n + 1, vector<int>(m + 1, 0)); // Precompute prefix sums for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + matrix[i - 1][j - 1]; } } // Iterate over all submatrices for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { for (int k = i; k <= n; k++) { for (int l = j; l <= m; l++) { // Calculate sum of // submatrix int sum = prefixSum[k][l] - prefixSum[i - 1][l] - prefixSum[k][j - 1] + prefixSum[i - 1][j - 1]; // Check if sum is odd // and number of // elements is odd if (sum % 2 == 1 && ((k - i + 1) * (l - j + 1)) % 2 == 1) { count++; } } } } } return count;}// Drivers codeint main(){ vector<vector<int> > matrix = { { 1, 2, 3 }, { 7, 5, 9 }, { 6, 8, 10 } }; int count = countOddSumSubmatrices(matrix); // Function Call cout << "Number of odd sum submatrices with odd number " "of elements: " << count << endl; return 0;} |
Java
import java.util.*;public class Main { public static int countOddSumSubmatrices(int[][] matrix) { int n = matrix.length; int m = matrix[0].length; int count = 0; // Initialize prefix sum matrix int[][] prefixSum = new int[n + 1][m + 1]; // Precompute prefix sums for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + matrix[i - 1][j - 1]; } } // Iterate over all submatrices for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { for (int k = i; k <= n; k++) { for (int l = j; l <= m; l++) { // Calculate sum of submatrix int sum = prefixSum[k][l] - prefixSum[i - 1][l] - prefixSum[k][j - 1] + prefixSum[i - 1][j - 1]; // Check if sum is odd and the number of elements is odd if (sum % 2 == 1 && ((k - i + 1) * (l - j + 1)) % 2 == 1) { count++; } } } } } return count; } public static void main(String[] args) { int[][] matrix = {{1, 2, 3}, {7, 5, 9}, {6, 8, 10}}; int count = countOddSumSubmatrices(matrix); // Function Call System.out.println("Number of odd sum submatrices with an odd number of elements: " + count); }} |
Python3
def count_odd_sum_submatrices(matrix): n = len(matrix) m = len(matrix[0]) count = 0 # Initialize the prefix sum matrix prefix_sum = [[0] * (m + 1) for _ in range(n + 1)] # Precompute prefix sums for i in range(1, n + 1): for j in range(1, m + 1): prefix_sum[i][j] = prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1] + matrix[i - 1][j - 1] # Iterate over all submatrices for i in range(1, n + 1): for j in range(1, m + 1): for k in range(i, n + 1): for l in range(j, m + 1): # Calculate the sum of the submatrix submatrix_sum = prefix_sum[k][l] - prefix_sum[i - 1][l] - prefix_sum[k][j - 1] + prefix_sum[i - 1][j - 1] # Check if the sum is odd and the number of elements is odd if submatrix_sum % 2 == 1 and ((k - i + 1) * (l - j + 1)) % 2 == 1: count += 1 return count# Driver's codeif __name__ == "__main__": matrix = [ [1, 2, 3], [7, 5, 9], [6, 8, 10] ] count = count_odd_sum_submatrices(matrix) # Function Call print(f"Number of odd sum submatrices with an odd number of elements: {count}") |
C#
using System;class GFG{ static int countOddSumSubmatrices(int[][] matrix) { int n = matrix.Length; int m = matrix[0].Length; int count = 0; // Initialize prefix sum matrix int[][] prefixSum = new int[n + 1][]; for (int i = 0; i <= n; i++) { prefixSum[i] = new int[m + 1]; } // Precompute prefix sums for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + matrix[i - 1][j - 1]; } } // Iterate over all submatrices for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { for (int k = i; k <= n; k++) { for (int l = j; l <= m; l++) { // Calculate sum of submatrix int sum = prefixSum[k][l] - prefixSum[i - 1][l] - prefixSum[k][j - 1] + prefixSum[i - 1][j - 1]; // Check if sum is odd and number of elements is odd if (sum % 2 == 1 && ((k - i + 1) * (l - j + 1)) % 2 == 1) { count++; } } } } } return count; } public static void Main() { int[][] matrix = { new int[] { 1, 2, 3 }, new int[] { 7, 5, 9 }, new int[] { 6, 8, 10 } }; int count = countOddSumSubmatrices(matrix); // Function Call Console.WriteLine("Number of odd sum submatrices with odd number of elements: " + count); }} |
Javascript
function countOddSumSubmatrices(matrix) { const n = matrix.length; const m = matrix[0].length; let count = 0; // Initialize prefix sum matrix const prefixSum = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0)); // Precompute prefix sums for (let i = 1; i <= n; i++) { for (let j = 1; j <= m; j++) { prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + matrix[i - 1][j - 1]; } } // Iterate over all submatrices for (let i = 1; i <= n; i++) { for (let j = 1; j <= m; j++) { for (let k = i; k <= n; k++) { for (let l = j; l <= m; l++) { // Calculate sum of submatrix const sum = prefixSum[k][l] - prefixSum[i - 1][l] - prefixSum[k][j - 1] + prefixSum[i - 1][j - 1]; // Check if sum is odd and the number of elements is odd if (sum % 2 === 1 && ((k - i + 1) * (l - j + 1)) % 2 === 1) { count++; } } } } } return count;}// Driver codeconst matrix = [ [1, 2, 3], [7, 5, 9], [6, 8, 10]];const count = countOddSumSubmatrices(matrix);// Function callconsole.log("Number of odd sum submatrices with odd number of elements: " + count); |
Output
Number of odd sum submatrices with odd number of elements: 8
Time Complexity: O(N4), as 4 nested for loop
Auxiliary Space: O(N2), extra space needed for prefix matrix.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
