Given a square matrix M[][] of size N*N, the task is to reduce that matrix into a matrix of size (N-1) * (N-1) using the following operation:
- Take all the 2×2 submatrix from N*N matrix,
- Insert sum of each submatrix to the resultant matrix L[ ][ ] of size N-1 * N-1 at the corresponding position.
Examples:
Input: M[][] = {{ 1, 2, 3, 4 },
{ 4, 5, 6, 7 },
{ 7, 8, 9, 10 },
{ 10, 11, 12, 13 }}
Output: L[][] = {{12, 16, 20},
{24, 28, 32},
{36, 40, 44}}
Explanation:
Input: M[][] = {{ 3, 6, 3},
{ 4, 7, 6},
{ 2, 1, 9}}
Output: L[][] = {{20, 22},
{14, 23}}
Approach: The task can be solved by simulating the process of the defined operation. Follow the below steps to solve the problem:
- Declare empty array l[] to store element of reduced matrix
- Declare c = s = 0, s for taking sum and c for changing column and p[ ] for storing sum after every iteration.
- Now s is, s = M[ i ][ c ] + M[ i ][ c + 1 ] + M[ i + 1 ][ c ] + M[ i+1 ][ c+1 ]
- It will store 4 elements, like element at index [00, 01, 10, 11], then [01, 02, 11, 12] similarly from row 2 and 3
- Store the first sum in array p[] and increment c and again assign s=0.
- Repeat step 3, hence we will get array p [ ].
- Store p in matrix l [ ] and repeat step 2.
Below is the implementation of the approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the desired matrixvector<vector<int> > checkMat(vector<vector<int> >& M, int N){// Empty array to store 2x2 matrix elementvector<vector<int> > l;for (int i = 0; i < N - 1; i++) { // Initialization int c = 0, s = 0; vector<int> p; for (int j = 0; j < N - 1; j++) { // Taking sum of 4 elements s += M[i][j] + M[i][j+1]; s += M[i + 1][j] + M[i + 1][j+1]; // Appending sum in array p p.push_back(s); // Assigning s to 0, to take sum // of another 4 element s = 0; // Increment c c++; } // Append array p[] to l l.push_back(p);}return l;}// Driver codeint main(){// Original matrixvector<vector<int> > M = { { 1, 2, 3, 4 }, { 4, 5, 6, 7 }, { 7, 8, 9, 10 }, { 10, 11, 12, 13 } };// Size of matrixint N = M.size();// Calling functionvector<vector<int> > res = checkMat(M, N);// Printing the resultfor (int i = 0; i < res.size(); i++) { for (int j = 0; j < res[i].size(); j++) { cout << res[i][j] << " "; } cout << "\n";}}// This code is contributed by Taranpreet and improved by prophet1999 |
Java
// Java code for the above approachimport java.util.*;class GFG{// Function to find the desired matrixstatic ArrayList<ArrayList<Integer> > checkMat(int[][] M, int N){ // Empty array to store 2x2 matrix element ArrayList<ArrayList<Integer> > l = new ArrayList<ArrayList<Integer> >(2); for (int i = 0; i < N - 1; i++) { // Initialization ArrayList<Integer> p = new ArrayList<Integer>(); int c = 0, s = 0; for (int j = 0; j < N - 1; j++) { // Taking sum of 4 elements s += M[i][j] + M[i][j+1]; s += M[i + 1][j] + M[i + 1][j+1]; // Appending sum in array p p.add(s); // Assigning s to 0, to take sum // of another 4 element s = 0; // Increment c c++; } // Append array p[] to l l.add(p); } return l;}public static void main(String[] args){ // Original matrix int[][] M = { { 1, 2, 3, 4 }, { 4, 5, 6, 7 }, { 7, 8, 9, 10 }, { 10, 11, 12, 13 } }; // Size of matrix int N = M.length; // Calling function ArrayList<ArrayList<Integer> > res = checkMat(M, N); // Printing the result for (int i = 0; i < res.size(); i++) { for (int j = 0; j < res.get(i).size(); j++) { System.out.print(res.get(i).get(j) + " "); } System.out.println(); }}}// This code is contributed by Potta Lokesh and improved by prophet1999 |
Python3
# Python program for the above approach# Function to find the desired matrixdef checkMat(M, N): # Empty array to store 2x2 matrix element l = [] for i in range(N-1): # Initialization c = s = 0 p = [] for j in range(N-1): # Taking sum of 4 elements s += M[i][j]+M[i][j+1] s += M[i + 1][j]+M[i + 1][j+1] # Appending sum in array p p.append(s) # Assigning s to 0, to take sum # of another 4 element s = 0 # Increment c c += 1 # Append array p[] to l l.append(p) return l# Driver codeif __name__ == "__main__": # Original matrix M = [[1, 2, 3, 4], [4, 5, 6, 7], [7, 8, 9, 10], [10, 11, 12, 13]] # Size of matrix N = len(M) # Calling function res = checkMat(M, N) # Printing the result for i in res: print(*i)# this code is improved by prophet1999 |
C#
// C# code for the above approachusing System;using System.Collections.Generic; public class GFG { // Function to find the desired matrix static List<List<int> > checkMat(int[,] M, int N) { // Empty array to store 2x2 matrix element List<List<int> > l = new List<List<int> >(2); for (int i = 0; i < N - 1; i++) { // Initialization List<int> p = new List<int>(); int c = 0, s = 0; for (int j = 0; j < N - 1; j++) { // Taking sum of 4 elements s += M[i,c] + M[i,c + 1]; s += M[i + 1,c] + M[i + 1,c + 1]; // Appending sum in array p p.Add(s); // Assigning s to 0, to take sum // of another 4 element s = 0; // Increment c c++; } // Append array p[] to l l.Add(p); } return l; } public static void Main(String[] args) { // Original matrix int[,] M = { { 1, 2, 3, 4 }, { 4, 5, 6, 7 }, { 7, 8, 9, 10 }, { 10, 11, 12, 13 } }; // Size of matrix int N = M.GetLength(0); // Calling function List<List<int> > res = checkMat(M, N); // Printing the result for (int i = 0; i < res.Count; i++) { for (int j = 0; j < res[i].Count; j++) { Console.Write(res[i][j] + " "); } Console.WriteLine(); } }}// This code is contributed by 29AjayKumar and improved by prophet1999 |
Javascript
<script> // JavaScript program for the above approach // Function to find the desired matrix const checkMat = (M, N) => { // Empty array to store 2x2 matrix element let l = []; for (let i = 0; i < N - 1; ++i) { // Initialization let c = s = 0; let p = []; for (let j = 0; j < N - 1; ++j) { // Taking sum of 4 elements s += M[i][j] + M[i][j+1]; s += M[i + 1][j] + M[i + 1][j+1]; // Appending sum in array p p.push(s); // Assigning s to 0, to take sum // of another 4 element s = 0; // Increment c c += 1; } // document.write(p); // document.write("<br/>") // Append array p[] to l l.push(p); } return l; } // Driver code // Original matrix let M = [[1, 2, 3, 4], [4, 5, 6, 7], [7, 8, 9, 10], [10, 11, 12, 13]]; // Size of matrix let N = M.length; // Calling function let res = checkMat(M, N); // Printing the result for (let i in res) { for (let j in res[i]) { document.write(`${res[i][j]} `); } document.write("<br/>"); }// This code is contributed by rakeshsahni and improved by prophet1999</script> |
Output
12 16 20 24 28 32 36 40 44
Time Complexity: O(N*N)
Auxiliary Space: O(N*N)
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!
