Dada una array cuadrada M[][] de tamaño N*N , la tarea es reducir esa array a una array de tamaño (N-1) * (N-1) usando la siguiente operación:
- Tome toda la subarray 2 × 2 de la array N * N ,
- Inserte la suma de cada subarray en la array resultante L[ ][ ] de tamaño N-1 * N-1 en la posición correspondiente.
Ejemplos:
Entrada: M[][] = {{ 1, 2, 3, 4 },
{ 4, 5, 6, 7 },
{ 7, 8, 9, 10 },
{ 10, 11, 12, 13 }}
Salida : L[][]={{12, 16, 20},
{24, 28, 32},
{36, 40, 44}}
Explicación :
Entrada: M[][] = {{ 3, 6, 3},
{ 4, 7, 6},
{ 2, 1, 9}}
Salida: L[][] = {{20, 22},
{14 , 23}}
Enfoque: La tarea se puede resolver simulando el proceso de la operación definida. Siga los pasos a continuación para resolver el problema:
- Declare la array vacía l[] para almacenar el elemento de la array reducida
- Declare c = s = 0 , s para tomar sum y c para cambiar de columna y p[ ] para almacenar sum después de cada iteración.
- Ahora s es, s = M[ i ][ c ] + M[ i ][ c + 1 ] + M[ i + 1 ][ c ] + M[ i+1 ][ c+1 ]
- Almacenará 4 elementos, como elemento en el índice [00, 01, 10, 11], luego [01, 02, 11, 12] de manera similar desde la fila 2 y 3
- Almacene la primera suma en la array p[] e incremente c y nuevamente asigne s=0 .
- Repita el paso 3, por lo que obtendremos la array p [ ] .
- Almacene p en la array l [ ] y repita el paso 2.
A continuación se muestra la implementación del enfoque :
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the desired matrix
vector<vector<int> > checkMat(vector<vector<int> >& M,
int N)
{
// Empty array to store 2x2 matrix element
vector<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 code
int main()
{
// Original matrix
vector<vector<int> > M = { { 1, 2, 3, 4 },
{ 4, 5, 6, 7 },
{ 7, 8, 9, 10 },
{ 10, 11, 12, 13 } };
// Size of matrix
int N = M.size();
// Calling function
vector<vector<int> > res = checkMat(M, N);
// Printing the result
for (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 approach
import java.util.*;
class GFG
{
// Function to find the desired matrix
static 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 matrix def 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 code if __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 approach
using 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>
Producción
12 16 20 24 28 32 36 40 44
Complejidad temporal : O(N*N)
Espacio auxiliar : O(N*N)
Publicación traducida automáticamente
Artículo escrito por harshdeepmahajan88 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA