Dado un mat[][] de tamaño n X n , la tarea es encontrar un elemento X tal que si el recorrido en sentido contrario a las agujas del reloj comienza desde X , entonces el elemento final que se imprimirá es mat[n – 1][n – 1] .
El recorrido en sentido antihorario de la array, mat[][] =
{{1, 2, 3},
{4, 5, 6},
{7, 8, 9}}
comenzando en el elemento 5 será 5, 6, 3, 2, 1, 4, 7, 8, 9.
Ejemplos:
Entrada: mat[][] = {{1, 2}, {3, 4}}
Salida: 2
Si comenzamos a atravesar desde mat[0][1], es decir, 2
, terminaremos con el elemento en mat[1 ][1] que es 4.
Entrada: mat[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
Salida: 5
Enfoque: Comenzando desde el elemento en mat[n – 1][n – 1] , comience a atravesar la array en el orden opuesto, es decir, en el sentido de las agujas del reloj. Cuando se recorren todos los elementos de la array, el último elemento visitado será el resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
// Function to print last element
// Of given matrix
int printLastElement(int mat[][2], int n)
{
// Starting row index
int si = 0;
// Starting column index
int sj = 0;
// Ending row index
int ei = n - 1;
// Ending column index
int ej = n - 1;
// Track the move
int direction = 0;
// While starting index is less than ending
// row index or starting column index
// is less the ending column index
while (si < ei || sj < ej) {
// Switch cases for all direction
// Move under all cases for all
// directions
switch (direction % 4) {
case 0:
sj++;
break;
case 1:
ei--;
break;
case 2:
ej--;
break;
case 3:
si++;
break;
}
// Increment direction by one
// for each case
direction++;
}
// Finally return the last element
// If not found return 0
return mat[si][sj];
return 0;
}
// Driver code
int main()
{
int n = 2;
int mat[][2] = { { 1, 2 }, { 3, 4 } };
cout << printLastElement(mat, n);
return 0;
}
Java
// Java implementation of the approach
class GfG
{
// Function to print last element
// Of given matrix
static int printLastElement(int mat[][], int n)
{
// Starting row index
int si = 0;
// Starting column index
int sj = 0;
// Ending row index
int ei = n - 1;
// Ending column index
int ej = n - 1;
// Track the move
int direction = 0;
// While starting index is less than ending
// row index or starting column index
// is less the ending column index
while (si < ei || sj < ej)
{
// Switch cases for all direction
// Move under all cases for all
// directions
switch (direction % 4)
{
case 0:
sj++;
break;
case 1:
ei--;
break;
case 2:
ej--;
break;
case 3:
si++;
break;
}
// Increment direction by one
// for each case
direction++;
}
// Finally return the last element
// If not found return 0
return mat[si][sj];
}
// Driver code
public static void main(String[] args)
{
int n = 2;
int mat[][] = new int[][]{{ 1, 2 }, { 3, 4 }};
System.out.println(printLastElement(mat, n));
}
}
// This code is contributed by Prerna Saini
Python3
# Python 3 implementation of the approach # Function to print last element # Of given matrix def printLastElement(mat, n): # Starting row index si = 0 # Starting column index sj = 0 # Ending row index ei = n - 1 # Ending column index ej = n - 1 # Track the move direction = 0 # While starting index is less than ending # row index or starting column index # is less the ending column index while (si < ei or sj < ej): # Switch cases for all direction # Move under all cases for all # directions if (direction % 4 == 0): sj += 1 if (direction % 4 == 1): ei -= 1 if (direction % 4 == 2): ej -= 1 if (direction % 4 == 3): si += 1 # Increment direction by one # for each case direction += 1 # Finally return the last element # If not found return 0 return mat[si][sj] return 0 # Driver code if __name__ == '__main__': n = 2 mat = [[1, 2], [3, 4 ]] print(printLastElement(mat, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to print last element
// Of given matrix
static int printLastElement(int [,]mat, int n)
{
// Starting row index
int si = 0;
// Starting column index
int sj = 0;
// Ending row index
int ei = n - 1;
// Ending column index
int ej = n - 1;
// Track the move
int direction = 0;
// While starting index is less than ending
// row index or starting column index
// is less the ending column index
while (si < ei || sj < ej)
{
// Switch cases for all direction
// Move under all cases for all
// directions
switch (direction % 4)
{
case 0:
sj++;
break;
case 1:
ei--;
break;
case 2:
ej--;
break;
case 3:
si++;
break;
}
// Increment direction by one
// for each case
direction++;
}
// Finally return the last element
// If not found return 0
return mat[si, sj];
}
// Driver code
public static void Main()
{
int n = 2;
int [,]mat = {{ 1, 2 }, { 3, 4 }};
Console.WriteLine(printLastElement(mat, n));
}
}
// This code is contributed by Ryuga
PHP
<?php
// PHP implementation of the approach
// Function to print last element
// Of given matrix
function printLastElement($mat, $n)
{
// Starting row index
$si = 0;
// Starting column index
$sj = 0;
// Ending row index
$ei = $n - 1;
// Ending column index
$ej = $n - 1;
// Track the move
$direction = 0;
// While starting index is less than ending
// row index or starting column index
// is less the ending column index
while ($si < $ei || $sj < $ej)
{
// Switch cases for all direction
// Move under all cases for all
// directions
switch ($direction % 4)
{
case 0:
$sj++;
break;
case 1:
$ei--;
break;
case 2:
$ej--;
break;
case 3:
$si++;
break;
}
// Increment direction by one
// for each case
$direction++;
}
// Finally return the last element
// If not found return 0
return $mat[$si][$sj];
return 0;
}
// Driver code
$n = 2;
$mat = array(array(1, 2),
array(3, 4));
echo printLastElement($mat, $n);
// This code is contributed by Akanksha Rai
?>
Javascript
<script>
// JavaScript implementation of the approach
// Function to print last element
// Of given matrix
function printLastElement(mat , n) {
// Starting row index
var si = 0;
// Starting column index
var sj = 0;
// Ending row index
var ei = n - 1;
// Ending column index
var ej = n - 1;
// Track the move
var direction = 0;
// While starting index is less than ending
// row index or starting column index
// is less the ending column index
while (si < ei || sj < ej) {
// Switch cases for all direction
// Move under all cases for all
// directions
switch (direction % 4) {
case 0:
sj++;
break;
case 1:
ei--;
break;
case 2:
ej--;
break;
case 3:
si++;
break;
}
// Increment direction by one
// for each case
direction++;
}
// Finally return the last element
// If not found return 0
return mat[si][sj];
}
// Driver code
var n = 2;
var mat = [[ 1, 2 ], [ 3, 4 ] ];
document.write(printLastElement(mat, n));
// This code contributed by gauravrajput1
</script>
Producción:
2
Complejidad del tiempo: O(N 2 )
Espacio Auxiliar: O(1)