Dada una array arr[] que consta de N enteros y una array Q[][] , donde cada fila es una consulta de la forma {L, R} . La tarea de cada consulta es comprobar si el recuento de subarreglos crecientes y decrecientes en el rango [L, R] es el mismo o no. Si se determina que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: arr[] = {11, 13, 12, 14}, Q[][] = {{1, 4}, {2, 4}}
Salida:
No
Sí
Explicación:
Consulta 1: Hay dos subarreglos crecientes { 11, 13} y {12, 14} en el rango [1, 4]. Pero solo hay un subarreglo decreciente {13, 12} en el rango [1, 4].
Por lo tanto, imprima No.
Consulta 2: Solo hay un subarreglo creciente {12, 14} y un subarreglo decreciente {13, 12} en el rango [2, 4].
Por lo tanto, imprima Sí.Entrada: arr[] = {16, 24, 32, 18, 14}, Q = {{1, 5}, {2, 3}, {2, 4}}
Salida:
Sí
No
Sí
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todos los subarreglos posibles a partir del subarreglo {arr[L], arr[R]} y comprobar si el número de subarreglos crecientes y decrecientes es el mismo o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Complejidad de Tiempo: O(Q*N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, observe que cada subarreglo creciente es seguido por un subarreglo decreciente y viceversa, es decir, aumentan o disminuyen alternativamente. Por lo tanto, el número de subarreglos crecientes y decrecientes diferirá como máximo en 1 . Por lo tanto, la idea es verificar si el primer par y el último par de elementos del rango, ambos forman pares crecientes o no. Si se encuentra que es cierto, escriba “No” . De lo contrario, escriba «Sí» . Realice el paso anterior para cada consulta para obtener el resultado en O(1) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if given range
// have equal number of increasing
// as well as decreasing subarrays
void checkCount(int A[], int Q[][2],
int q)
{
// Traverse each query
for (int i = 0; i < q; i++) {
int L = Q[i][0];
int R = Q[i][1];
// For 0-based indexing
L--, R--;
// Condition for same count of
// increasing & decreasing subarray
if ((A[L] < A[L + 1])
!= (A[R - 1] < A[R])) {
cout << "Yes\n";
}
else {
cout << "No\n";
}
}
}
// Driver Code
int main()
{
int arr[] = { 11, 13, 12, 14 };
int Q[][2] = { { 1, 4 }, { 2, 4 } };
int q = sizeof(Q) / sizeof(Q[0]);
checkCount(arr, Q, q);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to check if given range
// have equal number of increasing
// as well as decreasing subarrays
static void checkCount(int A[], int Q[][],
int q)
{
// Traverse each query
for(int i = 0; i < q; i++)
{
int L = Q[i][0];
int R = Q[i][1];
// For 0-based indexing
L--;
R--;
// Condition for same count of
// increasing & decreasing subarray
if ((A[L] < A[L + 1]) !=
(A[R - 1] < A[R]))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 11, 13, 12, 14 };
int Q[][] = { { 1, 4 }, { 2, 4 } };
int q = Q.length;
checkCount(arr, Q, q);
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python3 program for the above approach
# Function to check if given range
# have equal number of increasing
# as well as decreasing subarrays
def checkCount(A, Q, q):
# Traverse each query
for i in range(q):
L = Q[i][0]
R = Q[i][1]
# For 0-based indexing
L -= 1
R -= 1
# Condition for same count of
# increasing & decreasing subarray
if ((A[L] < A[L + 1]) !=
(A[R - 1] < A[R])):
print("Yes")
else:
print("No")
# Driver Code
if __name__ == '__main__':
arr = [ 11, 13, 12, 14 ]
Q = [ [ 1, 4 ], [ 2, 4 ] ]
q = len(Q)
checkCount(arr, Q, q)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if given range
// have equal number of increasing
// as well as decreasing subarrays
static void checkCount(int[] A, int[,] Q,
int q)
{
// Traverse each query
for(int i = 0; i < q; i++)
{
int L = Q[i, 0];
int R = Q[i, 1];
// For 0-based indexing
L--;
R--;
// Condition for same count of
// increasing & decreasing subarray
if ((A[L] < A[L + 1]) !=
(A[R - 1] < A[R]))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// Driver Code
public static void Main()
{
int[] arr = { 11, 13, 12, 14 };
int[,] Q = { { 1, 4 }, { 2, 4 } };
int q = Q.GetLength(0);
checkCount(arr, Q, q);
}
}
// This code is contributed by code_hunt
Javascript
<script>
// JavaScript program for the above approach
// Function to check if given range
// have equal number of increasing
// as well as decreasing subarrays
function checkCount(A, Q, q)
{
// Traverse each query
for(let i = 0; i < q; i++)
{
let L = Q[i][0];
let R = Q[i][1];
// For 0-based indexing
L--;
R--;
// Condition for same count of
// increasing & decreasing subarray
if ((A[L] < A[L + 1]) !=
(A[R - 1] < A[R]))
{
document.write("Yes" + "<br/>");
}
else
{
document.write("No" + "<br/>");
}
}
}
// Driver Code
let arr = [ 11, 13, 12, 14 ];
let Q = [[ 1, 4 ], [ 2, 4 ]];
let q = Q.length;
checkCount(arr, Q, q);
</script>
No Yes
Tiempo Complejidad: O(Q)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por riyakhazanchi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA