Suma de partes no diagonales de una array cuadrada

Posted on by Rudeus Greyrat

Dada una array cuadrada de tamaño NXN , la tarea es encontrar la suma de todos los elementos en cada parte cuando la array se divide en cuatro partes a lo largo de sus diagonales. Los elementos de las diagonales no deben contarse en la suma.
Ejemplos: 
 

Entrada: arr[][] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}} 
Salida : 68 
Explicación: 
 

De la imagen de arriba, (1, 6, 11, 16) y (4, 7, 10, 13) son las diagonales. 
La suma de los elementos que se necesita encontrar es: 
Arriba: (2 + 3) = 5 
Izquierda: (5 + 9) = 14 
Abajo: (14 + 15) = 29 
Derecha: (8 + 12) = 20 
Por lo tanto, suma de todas las partes = 68.
Entrada: arr[][] = { {1, 3, 1, 5}, {2, 2, 4, 1}, {5, 0, 2, 3}, {1, 3, 1, 5}} 
Salida: 19 
 

Enfoque: La idea es utilizar la indexación para identificar los elementos en las diagonales. 
 

  1. En una array bidimensional , dos diagonales se identifican de la siguiente manera: 
    1. Diagonal principal : la primera diagonal tiene el índice de la fila igual al índice de la columna. 
       
Condition for Principal Diagonal:
The row-column condition is row = column.
  1.  
  2. Diagonal secundaria : la segunda diagonal tiene la suma del índice de fila y columna igual a N (tamaño de la array). 
     
Condition for Secondary Diagonal:
The row-column condition is row = numberOfRows - column -1
  1.  
  2. Después de identificar ambas diagonales, la array se puede dividir en dos partes utilizando la diagonal que pasa por el primer elemento de la última fila y el último elemento de la primera fila: 
    1. La parte izquierda: 
      • Si el índice de la columna es mayor que el índice de la fila, el elemento pertenece a la parte superior de la array.
      • Si el índice de fila es mayor que el índice de columna, el elemento pertenece a la parte izquierda de la array.
    2. La parte derecha: 
      • Si el índice de la columna es mayor que el índice de la fila, el elemento pertenece a la parte derecha de la array.
      • Si el índice de fila es mayor que el índice de columna, el elemento pertenece a la parte inferior de la array.

  1. Entonces, para obtener la suma de las partes no diagonales de la array: 
    • Atraviesa la array por filas
    • Si el elemento es parte de la diagonal, omita este elemento
    • Si el elemento es parte de la parte izquierda, derecha, inferior o superior (es decir, partes no diagonales), agregue el elemento en la suma resultante

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return a vector which
// consists the sum of
// four portions of the matrix
int sumOfParts(int* arr, int N)
{
    int sum_part1 = 0, sum_part2 = 0,
        sum_part3 = 0, sum_part4 = 0;
    int totalsum = 0;
 
    // Iterating through the matrix
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
 
            // Condition for selecting all values
            // before the second diagonal of metrics
            if (i + j < N - 1) {
 
                // Top portion of the matrix
                if (i < j and i != j and i + j)
                    sum_part1 += (arr + i * N)[j];
 
                // Left portion of the matrix
                else if (i != j)
                    sum_part2 += (arr + i * N)[j];
            }
            else {
 
                // Bottom portion of the matrix
                if (i > j and i + j != N - 1)
                    sum_part3 += (arr + i * N)[j];
 
                // Right portion of the matrix
                else {
                    if (i + j != N - 1 and i != j)
                        sum_part4 += (arr + i * N)[j];
                }
            }
        }
    }
 
    // Adding all the four portions into a vector
    totalsum = sum_part1 + sum_part2
               + sum_part3 + sum_part4;
    return totalsum;
}
 
// Driver code
int main()
{
    int N = 4;
    int arr[N][N] = { { 1, 2, 3, 4 },
                      { 5, 6, 7, 8 },
                      { 9, 10, 11, 12 },
                      { 13, 14, 15, 16 } };
 
    cout << sumOfParts((int*)arr, N);
}

Java

// Java implementation of the above approach
class GFG
{
  
// Function to return a vector which
// consists the sum of
// four portions of the matrix
static int sumOfParts(int[][] arr, int N)
{
    int sum_part1 = 0, sum_part2 = 0,
        sum_part3 = 0, sum_part4 = 0;
    int totalsum = 0;
  
    // Iterating through the matrix
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
  
            // Condition for selecting all values
            // before the second diagonal of metrics
            if (i + j < N - 1) {
  
                // Top portion of the matrix
                if (i < j && i != j && i + j > 0)
                    sum_part1 += arr[i][j];
  
                // Left portion of the matrix
                else if (i != j)
                    sum_part2 += arr[i][j];
            }
            else {
  
                // Bottom portion of the matrix
                if (i > j && i + j != N - 1)
                    sum_part3 += arr[i][j];
  
                // Right portion of the matrix
                else {
                    if (i + j != N - 1 && i != j)
                        sum_part4 += arr[i][j];
                }
            }
        }
    }
  
    // Adding all the four portions into a vector
    totalsum = sum_part1 + sum_part2
               + sum_part3 + sum_part4;
    return totalsum;
}
  
// Driver code
public static void main(String[] args)
{
    int N = 4;
    int arr[][] = { { 1, 2, 3, 4 },
                      { 5, 6, 7, 8 },
                      { 9, 10, 11, 12 },
                      { 13, 14, 15, 16 } };
  
    System.out.print(sumOfParts(arr, N));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 implementation of the above approach
 
# Function to return a vector which
# consists the sum of
# four portions of the matrix
def sumOfParts(arr,N):
    sum_part1, sum_part2, sum_part3, \
    sum_part4 = 0, 0, 0, 0
    totalsum = 0
 
    # Iterating through the matrix
    for i in range(N):
        for j in range(N):
             
            # Condition for selecting all values
            # before the second diagonal of metrics
            if i + j < N - 1:
                 
                # Top portion of the matrix
                if(i < j and i != j and i + j):
                    sum_part1 += arr[i][j]
                 
                # Left portion of the matrix
                elif i != j:
                    sum_part2 += arr[i][j]
            else:
                 
                # Bottom portion of the matrix
                if i > j and i + j != N - 1:
                    sum_part3 += arr[i][j]
                else:
                     
                # Right portion of the matrix
                    if i + j != N - 1 and i != j:
                        sum_part4 += arr[i][j]
        # Adding all the four portions into a vector
    return sum_part1 + sum_part2 + sum_part3 + sum_part4
 
# Driver code
N = 4
arr = [[ 1, 2, 3, 4 ],
       [ 5, 6, 7, 8 ],
       [ 9, 10, 11, 12 ],
       [ 13, 14, 15, 16 ]]
 
print(sumOfParts(arr, N))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the above approach
using System;
 
class GFG
{
  
    // Function to return a vector which
    // consists the sum of
    // four portions of the matrix
    static int sumOfParts(int[,] arr, int N)
    {
        int sum_part1 = 0, sum_part2 = 0,
            sum_part3 = 0, sum_part4 = 0;
        int totalsum = 0;
      
        // Iterating through the matrix
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
      
                // Condition for selecting all values
                // before the second diagonal of metrics
                if (i + j < N - 1) {
      
                    // Top portion of the matrix
                    if (i < j && i != j && i + j > 0)
                        sum_part1 += arr[i, j];
      
                    // Left portion of the matrix
                    else if (i != j)
                        sum_part2 += arr[i, j];
                }
                else {
      
                    // Bottom portion of the matrix
                    if (i > j && i + j != N - 1)
                        sum_part3 += arr[i, j];
      
                    // Right portion of the matrix
                    else {
                        if (i + j != N - 1 && i != j)
                            sum_part4 += arr[i, j];
                    }
                }
            }
        }
      
        // Adding all the four portions into a vector
        totalsum = sum_part1 + sum_part2
                   + sum_part3 + sum_part4;
        return totalsum;
    }
      
    // Driver code
    public static void Main()
    {
        int N = 4;
        int [,]arr = { { 1, 2, 3, 4 },
                          { 5, 6, 7, 8 },
                          { 9, 10, 11, 12 },
                          { 13, 14, 15, 16 } };
      
        Console.WriteLine(sumOfParts(arr, N));
    }
}
 
// This code is contributed by Yash_R

Javascript

<script>
 
// javascript implementation of the above approach
 
  
// Function to return a vector which
// consists the sum of
// four portions of the matrix
function sumOfParts(arr , N)
{
    var sum_part1 = 0, sum_part2 = 0,
        sum_part3 = 0, sum_part4 = 0;
    var totalsum = 0;
  
    // Iterating through the matrix
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
  
            // Condition for selecting all values
            // before the second diagonal of metrics
            if (i + j < N - 1) {
  
                // Top portion of the matrix
                if (i < j && i != j && i + j > 0)
                    sum_part1 += arr[i][j];
  
                // Left portion of the matrix
                else if (i != j)
                    sum_part2 += arr[i][j];
            }
            else {
  
                // Bottom portion of the matrix
                if (i > j && i + j != N - 1)
                    sum_part3 += arr[i][j];
  
                // Right portion of the matrix
                else {
                    if (i + j != N - 1 && i != j)
                        sum_part4 += arr[i][j];
                }
            }
        }
    }
  
    // Adding all the four portions into a vector
    totalsum = sum_part1 + sum_part2
               + sum_part3 + sum_part4;
    return totalsum;
}
  
// Driver code
var N = 4;
var arr = [ [ 1, 2, 3, 4 ],
                  [ 5, 6, 7, 8 ],
                  [ 9, 10, 11, 12 ],
                  [ 13, 14, 15, 16 ] ];
 
document.write(sumOfParts(arr, N));
 
// This code is contributed by 29AjayKumar
 
</script>
Producción: 

68

 

Complejidad de tiempo: O(N 2 ) ya que estamos atravesando la array completa por filas.

Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por manthanpandey039 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *