Dada una array de orden impar, es decir (5*5). La tarea es verificar si el elemento central de la array es igual a la suma individual de todas las medias diagonales.
Ejemplos:
Input : mat[][] = { 2 9 1 4 -2
6 7 2 11 4
4 2 9 2 4
1 9 2 4 4
0 2 4 2 5 }
Output :Yes
Explanation :
Sum of Half Diagonal 1 = 2 + 7 = 9
Sum of Half Diagonal 2 = 9 + 0 = 9
Sum of Half Diagonal 3 = 11 + -2 = 9
Sum of Half Diagonal 4 = 5 + 4 = 9
Here, All the sums equal to the center element
that is mat[2][2] = 9
Enfoque simple:
iterar dos bucles, encontrar todas las sumas de la mitad de la diagonal y luego verificar que todas las sumas sean iguales al elemento central de la array o no. Si alguno de ellos no es igual al elemento central, escriba «No» De lo contrario, «Sí».
Complejidad de tiempo: O(N*N)
Enfoque eficiente: se basa en el enfoque eficiente para encontrar la suma diagonal en O(N) .
A continuación se muestra la implementación de este enfoque.
C++
// C++ Program to check if the center
// element is equal to the individual
// sum of all the half diagonals
#include <stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int MAX = 100;
// Function to Check center element
// is equal to the individual
// sum of all the half diagonals
bool HalfDiagonalSums(int mat[][MAX], int n)
{
// Find sums of half diagonals
int diag1_left = 0, diag1_right = 0;
int diag2_left = 0, diag2_right = 0;
for (int i = 0, j = n - 1; i < n; i++, j--) {
if (i < n/2) {
diag1_left += mat[i][i];
diag2_left += mat[j][i];
}
else if (i > n/2) {
diag1_right += mat[i][i];
diag2_right += mat[j][i];
}
}
return (diag1_left == diag2_right &&
diag2_right == diag2_left &&
diag1_right == diag2_left &&
diag2_right == mat[n/2][n/2]);
}
// Driver code
int main()
{
int a[][MAX] = { { 2, 9, 1, 4, -2},
{ 6, 7, 2, 11, 4},
{ 4, 2, 9, 2, 4},
{ 1, 9, 2, 4, 4},
{ 0, 2, 4, 2, 5} };
cout << ( HalfDiagonalSums(a, 5) ? "Yes" : "No" );
return 0;
}
Java
// Java program to find maximum elements
// that can be made equal with k updates
import java.util.Arrays;
public class GFG {
static int MAX = 100;
// Function to Check center element
// is equal to the individual
// sum of all the half diagonals
static boolean HalfDiagonalSums(int mat[][],
int n)
{
// Find sums of half diagonals
int diag1_left = 0, diag1_right = 0;
int diag2_left = 0, diag2_right = 0;
for (int i = 0, j = n - 1; i < n;
i++, j--)
{
if (i < n/2) {
diag1_left += mat[i][i];
diag2_left += mat[j][i];
}
else if (i > n/2) {
diag1_right += mat[i][i];
diag2_right += mat[j][i];
}
}
return (diag1_left == diag2_right &&
diag2_right == diag2_left &&
diag1_right == diag2_left &&
diag2_right == mat[n/2][n/2]);
}
// Driver code
public static void main(String args[])
{
int a[][] = { { 2, 9, 1, 4, -2},
{ 6, 7, 2, 11, 4},
{ 4, 2, 9, 2, 4},
{ 1, 9, 2, 4, 4},
{ 0, 2, 4, 2, 5} };
System.out.print ( HalfDiagonalSums(a, 5)
? "Yes" : "No" );
}
}
// This code is contributed by Sam007
Python 3
# Python 3 Program to check if the center
# element is equal to the individual
# sum of all the half diagonals
MAX = 100
# Function to Check center element
# is equal to the individual
# sum of all the half diagonals
def HalfDiagonalSums( mat, n):
# Find sums of half diagonals
diag1_left = 0
diag1_right = 0
diag2_left = 0
diag2_right = 0
i = 0
j = n - 1
while i < n:
if (i < n//2) :
diag1_left += mat[i][i]
diag2_left += mat[j][i]
elif (i > n//2) :
diag1_right += mat[i][i]
diag2_right += mat[j][i]
i += 1
j -= 1
return (diag1_left == diag2_right and
diag2_right == diag2_left and
diag1_right == diag2_left and
diag2_right == mat[n//2][n//2])
# Driver code
if __name__ == "__main__":
a = [[2, 9, 1, 4, -2],
[6, 7, 2, 11, 4],
[ 4, 2, 9, 2, 4],
[1, 9, 2, 4, 4 ],
[ 0, 2, 4, 2, 5]]
print("Yes") if (HalfDiagonalSums(a, 5)) else print("No" )
C#
// C# program to find maximum
// elements that can be made
// equal with k updates
using System;
class GFG
{
// Function to Check
// center element is
// equal to the individual
// sum of all the half
// diagonals
static bool HalfDiagonalSums(int [,]mat,
int n)
{
// Find sums of
// half diagonals
int diag1_left = 0,
diag1_right = 0;
int diag2_left = 0,
diag2_right = 0;
for (int i = 0, j = n - 1;
i < n; i++, j--)
{
if (i < n / 2)
{
diag1_left += mat[i, i];
diag2_left += mat[j, i];
}
else if (i > n / 2)
{
diag1_right += mat[i, i];
diag2_right += mat[j, i];
}
}
return (diag1_left == diag2_right &&
diag2_right == diag2_left &&
diag1_right == diag2_left &&
diag2_right == mat[n / 2, n / 2]);
}
// Driver code
static public void Main ()
{
int [,]a = {{ 2, 9, 1, 4, -2},
{ 6, 7, 2, 11, 4},
{ 4, 2, 9, 2, 4},
{ 1, 9, 2, 4, 4},
{ 0, 2, 4, 2, 5}};
Console.WriteLine(HalfDiagonalSums(a, 5)?
"Yes" : "No" );
}
}
// This code is contributed by ajit
PHP
<?php
// PHP Program to check if
// the center element is
// equal to the individual
// sum of all the half diagonals
$MAX = 100;
// Function to Check center
// element is equal to the
// individual sum of all
// the half diagonals
function HalfDiagonalSums($mat, $n)
{
global $MAX ;
// Find sums of
// half diagonals
$diag1_left = 1; $diag1_right = 1;
$diag2_left = 1; $diag2_right = 1;
for ($i = 0, $j = $n - 1;
$i < $n; $i++, $j--)
{
if ($i < $n / 2)
{
$diag1_left += $mat[$i][$i];
$diag2_left += $mat[$j][$i];
}
else if ($i > $n / 2)
{
$diag1_right += $mat[$i][$i];
$diag2_right += $mat[$j][$i];
}
}
return ($diag1_left == $diag2_right &&
$diag2_right == $diag2_left &&
$diag1_right == $diag2_left &&
$diag2_right == $mat[$n / 2][$n / 2]);
}
// Driver code
$a = array(array(2, 9, 1, 4, -2),
array(6, 7, 2, 11, 4),
array(4, 2, 9, 2, 4),
array(1, 9, 2, 4, 4),
array(0, 2, 4, 2, 5));
if(HalfDiagonalSums($a, 5) == 0)
echo "Yes" ;
else
echo "No" ;
// This code is contributed
// by akt_mit
?>
Javascript
<script>
// Javascript Program to check if the center
// element is equal to the individual
// sum of all the half diagonals
const MAX = 100;
// Function to Check center element
// is equal to the individual
// sum of all the half diagonals
function HalfDiagonalSums(mat, n)
{
// Find sums of half diagonals
let diag1_left = 0, diag1_right = 0;
let diag2_left = 0, diag2_right = 0;
for (let i = 0, j = n - 1; i < n; i++, j--) {
if (i < parseInt(n/2)) {
diag1_left += mat[i][i];
diag2_left += mat[j][i];
}
else if (i > parseInt(n/2)) {
diag1_right += mat[i][i];
diag2_right += mat[j][i];
}
}
return (diag1_left == diag2_right &&
diag2_right == diag2_left &&
diag1_right == diag2_left &&
diag2_right == mat[parseInt(n/2)][parseInt(n/2)]);
}
// Driver code
let a = [ [ 2, 9, 1, 4, -2],
[ 6, 7, 2, 11, 4],
[ 4, 2, 9, 2, 4],
[ 1, 9, 2, 4, 4],
[ 0, 2, 4, 2, 5] ];
document.write( HalfDiagonalSums(a, 5) ? "Yes" : "No" );
// This code is contributed by subham348.
</script>
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.