Dada una array m[][] , la tarea es comprobar si la array dada es bitónica inversa o no. Si la array dada es Bitónica inversa, imprima Sí . De lo contrario , imprima No.
Si todas las filas y las columnas de la array dada tienen elementos en uno de los siguientes órdenes:
- Estrictamente creciente
- estrictamente decreciente
- Estrictamente decreciente seguido de estrictamente creciente
Entonces se dice que la array dada es una array bitónica inversa
Ejemplos :
Entrada: m[][] = {{2, 3, 4}, {1, 2, 3}, {4, 5, 6} }
Salida: Sí
Explicación:
Todas las filas de la array dada forman una secuencia creciente.
Todas las columnas de la array dada {2, 1, 4}, {3, 2, 5}, {4, 3, 6} forman una secuencia decreciente seguida de una secuencia creciente.
Por lo tanto, la array es bitónica inversa.
Entrada: m[][] = {{1, 2, 3}, {4, 5, 6}, {2, 5, 4}}
Salida: No
Explicación:
Dado que la columna {1, 4, 2} no satisface cualquiera de las tres condiciones, la array dada no es bitónica inversa.
Enfoque :
siga los pasos a continuación para resolver el problema:
- Verifique los elementos de cada fila de la array uno por uno, si forma una secuencia bitónica inversa o no. Si se encuentra que alguna fila no es bitónica inversa , imprima No.
- Del mismo modo, verifique los elementos de cada columna uno por uno, si forma una secuencia bitónica inversa o no. Si se encuentra que alguna fila no es bitónica inversa , imprima No.
- Si se encuentra que todas las filas y columnas son bitónicas inversas , imprima Sí.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to check if a
// matrix is Reverse Bitonic or not
#include <bits/stdc++.h>
using namespace std;
const int N = 3, M = 3;
// Function to check if an
// array is Reverse Bitonic or not
bool checkReverseBitonic(int arr[], int n)
{
int i, j, f = 0;
// Check for decreasing sequence
for (i = 1; i < n; i++) {
if (arr[i] < arr[i - 1])
continue;
if (arr[i] == arr[i - 1])
return false;
else {
f = 1;
break;
}
}
if (i == n)
return true;
// Check for increasing sequence
for (j = i + 1; j < n; j++) {
if (arr[j] > arr[j - 1])
continue;
if (arr[i] == arr[i - 1])
return false;
else {
if (f == 1)
return false;
}
}
return true;
}
// Function to check whether given
// matrix is bitonic or not
void check(int arr[N][M])
{
int f = 0;
// Check row-wise
for (int i = 0; i < N; i++) {
if (!checkReverseBitonic(arr[i], M)) {
cout << "No" << endl;
return;
}
}
// Check column wise
for (int i = 0; i < N; i++) {
// Generate an array
// consisting of elements
// of the current column
int temp[N];
for (int j = 0; j < N; j++) {
temp[j] = arr[j][i];
}
if (!checkReverseBitonic(temp, N)) {
cout << "No" << endl;
return;
}
}
cout << "Yes";
}
// Driver Code
int main()
{
int m[N][M] = { { 2, 3, 4 },
{ 1, 2, 3 },
{ 4, 5, 6 } };
check(m);
return 0;
}
Java
// Java Program to check if a
// matrix is Reverse Bitonic or not
import java.util.*;
class GFG{
static int N = 3, M = 3;
// Function to check if an
// array is Reverse Bitonic or not
static boolean checkReverseBitonic(int arr[], int n)
{
int i, j, f = 0;
// Check for decreasing sequence
for (i = 1; i < n; i++)
{
if (arr[i] < arr[i - 1])
continue;
if (arr[i] == arr[i - 1])
return false;
else
{
f = 1;
break;
}
}
if (i == n)
return true;
// Check for increasing sequence
for (j = i + 1; j < n; j++)
{
if (arr[j] > arr[j - 1])
continue;
if (arr[i] == arr[i - 1])
return false;
else
{
if (f == 1)
return false;
}
}
return true;
}
// Function to check whether given
// matrix is bitonic or not
static void check(int arr[][])
{
int f = 0;
// Check row-wise
for (int i = 0; i < N; i++)
{
if (!checkReverseBitonic(arr[i], M))
{
System.out.print("No" + "\n");
return;
}
}
// Check column wise
for (int i = 0; i < N; i++)
{
// Generate an array
// consisting of elements
// of the current column
int temp[] = new int[N];
for (int j = 0; j < N; j++)
{
temp[j] = arr[j][i];
}
if (!checkReverseBitonic(temp, N))
{
System.out.print("No" + "\n");
return;
}
}
System.out.print("Yes");
}
// Driver Code
public static void main(String[] args)
{
int m[][] = { { 2, 3, 4 },
{ 1, 2, 3 },
{ 4, 5, 6 } };
check(m);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to check if a
# matrix is Reverse Bitonic or not
N = 3
M = 3
# Function to check if an
# array is Reverse Bitonic or not
def checkReverseBitonic(arr, n):
f = 0
# Check for decreasing sequence
for i in range(1, n):
if (arr[i] < arr[i - 1]):
continue
if (arr[i] == arr[i - 1]):
return False
else:
f = 1
break
if (i == n):
return True
# Check for increasing sequence
for j in range(i + 1, n):
if (arr[j] > arr[j - 1]):
continue
if (arr[i] == arr[i - 1]):
return False
else:
if (f == 1):
return False
return True
# Function to check whether given
# matrix is bitonic or not
def check(arr):
f = 0
# Check row-wise
for i in range (N):
if (not checkReverseBitonic(arr[i], M)):
print("No")
return
# Check column wise
for i in range(N):
# Generate an array
# consisting of elements
# of the current column
temp = [0] * N
for j in range(N):
temp[j] = arr[j][i]
if (not checkReverseBitonic(temp, N)):
print("No")
return
print("Yes")
# Driver Code
if __name__ == "__main__":
m = [ [ 2, 3, 4 ],
[ 1, 2, 3 ],
[ 4, 5, 6 ] ]
check(m)
# This code is contributed by chitranayal
C#
// C# Program to check if a
// matrix is Reverse Bitonic or not
using System;
class GFG{
static int N = 3, M = 3;
// Function to check if an
// array is Reverse Bitonic or not
static bool checkReverseBitonic(int []arr, int n)
{
int i, j, f = 0;
// Check for decreasing sequence
for (i = 1; i < n; i++)
{
if (arr[i] < arr[i - 1])
continue;
if (arr[i] == arr[i - 1])
return false;
else
{
f = 1;
break;
}
}
if (i == n)
return true;
// Check for increasing sequence
for (j = i + 1; j < n; j++)
{
if (arr[j] > arr[j - 1])
continue;
if (arr[i] == arr[i - 1])
return false;
else
{
if (f == 1)
return false;
}
}
return true;
}
// Function to check whether given
// matrix is bitonic or not
static void check(int [,]arr)
{
// Check row-wise
for (int i = 0; i < N; i++)
{
if (!checkReverseBitonic(GetRow(arr, i), M))
{
Console.Write("No" + "\n");
return;
}
}
// Check column wise
for (int i = 0; i < N; i++)
{
// Generate an array
// consisting of elements
// of the current column
int []temp = new int[N];
for (int j = 0; j < N; j++)
{
temp[j] = arr[j,i];
}
if (!checkReverseBitonic(temp, N))
{
Console.Write("No" + "\n");
return;
}
}
Console.Write("Yes");
}
public static int[] GetRow(int[,] matrix, int row)
{
var rowLength = matrix.GetLength(1);
var rowVector = new int[rowLength];
for (var i = 0; i < rowLength; i++)
rowVector[i] = matrix[row, i];
return rowVector;
}
// Driver Code
public static void Main(String[] args)
{
int [,]m = {{ 2, 3, 4 },
{ 1, 2, 3 },
{ 4, 5, 6 }};
check(m);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Java script Program to check if a
// matrix is Reverse Bitonic or not
let N = 3, M = 3;
// Function to check if an
// array is Reverse Bitonic or not
function checkReverseBitonic(arr,n)
{
let i, j, f = 0;
// Check for decreasing sequence
for (i = 1; i < n; i++)
{
if (arr[i] < arr[i - 1])
continue;
if (arr[i] == arr[i - 1])
return false;
else
{
f = 1;
break;
}
}
if (i == n)
return true;
// Check for increasing sequence
for (j = i + 1; j < n; j++)
{
if (arr[j] > arr[j - 1])
continue;
if (arr[i] == arr[i - 1])
return false;
else
{
if (f == 1)
return false;
}
}
return true;
}
// Function to check whether given
// matrix is bitonic or not
function check(arr)
{
let f = 0;
// Check row-wise
for (let i = 0; i < N; i++)
{
if (!checkReverseBitonic(arr[i], M))
{
document.write("No" + "<br>");
return;
}
}
// Check column wise
for (let i = 0; i < N; i++)
{
// Generate an array
// consisting of elements
// of the current column
let temp= [N];
for (let j = 0; j < N; j++)
{
temp[j] = arr[j][i];
}
if (!checkReverseBitonic(temp, N))
{
document.write("No" + "<br>");
return;
}
}
document.write("Yes");
}
// Driver Code
let m = [[ 2, 3, 4 ],
[ 1, 2, 3 ],
[ 4, 5, 6 ]];
check(m);
// This code is contributed by sravan kumar
</script>
Producción:
Yes
Complejidad temporal: O(N × M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por grand_master y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA