Dada una array arr[] que consta de N enteros, la tarea es verificar si es posible hacer que la array dada aumente estrictamente eliminando como máximo un elemento. Si es posible hacer que la array sea estrictamente creciente, imprima «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: arr[] = {1, 1, 2}
Salida: Sí
Explicación: Eliminar una aparición de 1 modifica la array a {1, 2}, que es estrictamente una array creciente.Entrada: arr[] = {2, 2, 3, 4, 5, 5}
Salida: No
Enfoque: El problema dado se puede resolver recorriendo la array arr[] y contando los índices que satisfacen la condición arr[i-1] ≥ arr[i] . Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos contar como 0 e indexar como -1 , para almacenar el recuento de elementos necesarios para eliminar y el índice del elemento eliminado, respectivamente.
- Recorra la array dada sobre el rango [1, N – 1] y si el valor de arr[i – 1] es al menos arr[i] incremente el valor de count en 1 y actualice el valor del índice como i .
- Si el valor de la cuenta es mayor que 1 , imprima “ No” y regrese .
- De lo contrario, verifique las siguientes condiciones:
- Si el valor de count es igual a 0 , imprima «Sí» y devuelva .
- Si el índice es igual a (N – 1) o igual a 0 , imprima “Sí” y regrese.
- Compruebe si eliminar el elemento en el índice hace que arr[index – 1] < arr[index + 1] , luego imprima “ Sí” y regrese .
- Compruebe si eliminar el elemento en el índice – 1 hace que el arr[índice – 2] < arr[índice] , donde el índice – 2 >= 0 , luego imprima “Sí” y regrese .
- Compruebe si el índice < 0, luego imprima «Sí» y regrese.
- Después de completar los pasos anteriores, si no se cumple ninguno de los casos anteriores, imprima «No» .
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 find if is it possible
// to make the array strictly increasing
// by removing at most one element
bool check(int arr[], int n)
{
// Stores the count of numbers that
// are needed to be removed
int count = 0;
// Store the index of the element
// that needs to be removed
int index = -1;
// Traverse the range [1, N - 1]
for (int i = 1; i < n; i++) {
// If arr[i-1] is greater than
// or equal to arr[i]
if (arr[i - 1] >= arr[i]) {
// Increment the count by 1
count++;
// Update index
index = i;
}
}
// If count is greater than one
if (count > 1)
return false;
// If no element is removed
if (count == 0)
return true;
// If only the last or the
// first element is removed
if (index == n - 1 || index == 1)
return true;
// If a[index] is removed
if (arr[index - 1] < arr[index + 1])
return true;
// If a[index - 1] is removed
if (index - 2 >= 0 && arr[index - 2] < arr[index])
return true;
// if there is no element to compare
if(index < 0)
return true;
return false;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 5, 3, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
if (check(arr, N))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to find if is it possible
// to make the array strictly increasing
// by removing at most one element
public static boolean check(int arr[], int n)
{
// Stores the count of numbers that
// are needed to be removed
int count = 0;
// Store the index of the element
// that needs to be removed
int index = -1;
// Traverse the range [1, N - 1]
for(int i = 1; i < n; i++)
{
// If arr[i-1] is greater than
// or equal to arr[i]
if (arr[i - 1] >= arr[i])
{
// Increment the count by 1
count++;
// Update index
index = i;
}
}
// If count is greater than one
if (count > 1)
return false;
// If no element is removed
if (count == 0)
return true;
// If only the last or the
// first element is removed
if (index == n - 1 || index == 1)
return true;
// If a[index] is removed
if (arr[index - 1] < arr[index + 1])
return true;
// If a[index - 1] is removed
if (index - 2 >= 0 && arr[index - 2] < arr[index])
return true;
// if there is no element to compare
if(index < 0)
return true;
return false;
}
// Driver Code
public static void main(String args[])
{
int []arr = { 1, 2, 5, 3, 5 };
int N = arr.length;
if (check(arr, N))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by SoumikMondal
Python3
# Python3 program for the above approach
# Function to find if is it possible
# to make the array strictly increasing
# by removing at most one element
def check(arr, n):
# Stores the count of numbers that
# are needed to be removed
count = 0
# Store the index of the element
# that needs to be removed
index = -1
# Traverse the range [1, N - 1]
for i in range(1, n):
# If arr[i-1] is greater than
# or equal to arr[i]
if (arr[i - 1] >= arr[i]):
# Increment the count by 1
count += 1
# Update index
index = i
# If count is greater than one
if (count > 1):
return False
# If no element is removed
if (count == 0):
return True
# If only the last or the
# first element is removed
if (index == n - 1 or index == 1):
return True
# If a[index] is removed
if (arr[index - 1] < arr[index + 1]):
return True
# If a[index - 1] is removed
if (arr[index - 2] < arr[index]):
return True
return False
# Driver Code
if __name__ == '__main__':
arr = [1, 2, 5, 3, 5]
N = len(arr)
if (check(arr, N)):
print("Yes")
else:
print("No")
# This code is contributed by mohitkumar 29.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find if is it possible
// to make the array strictly increasing
// by removing at most one element
public static bool check(int[] arr, int n)
{
// Stores the count of numbers that
// are needed to be removed
int count = 0;
// Store the index of the element
// that needs to be removed
int index = -1;
// Traverse the range [1, N - 1]
for(int i = 1; i < n; i++)
{
// If arr[i-1] is greater than
// or equal to arr[i]
if (arr[i - 1] >= arr[i])
{
// Increment the count by 1
count++;
// Update index
index = i;
}
}
// If count is greater than one
if (count > 1)
return false;
// If no element is removed
if (count == 0)
return true;
// If only the last or the
// first element is removed
if (index == n - 1 || index == 1)
return true;
// If a[index] is removed
if (arr[index - 1] < arr[index + 1])
return true;
// If a[index - 1] is removed
if (arr[index - 2] < arr[index])
return true;
return false;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 1, 2, 5, 3, 5 };
int N = arr.Length;
if (check(arr, N))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript program for the above approach
// Function to find if is it possible
// to make the array strictly increasing
// by removing at most one element
function check(arr , n)
{
// Stores the count of numbers that
// are needed to be removed
var count = 0;
// Store the index of the element
// that needs to be removed
var index = -1;
// Traverse the range [1, N - 1]
for(i = 1; i < n; i++)
{
// If arr[i-1] is greater than
// or equal to arr[i]
if (arr[i - 1] >= arr[i])
{
// Increment the count by 1
count++;
// Update index
index = i;
}
}
// If count is greater than one
if (count > 1)
return false;
// If no element is removed
if (count == 0)
return true;
// If only the last or the
// first element is removed
if (index == n - 1 || index == 1)
return true;
// If a[index] is removed
if (arr[index - 1] < arr[index + 1])
return true;
// If a[index - 1] is removed
if (arr[index - 2] < arr[index])
return true;
return false;
}
// Driver Code
var arr = [ 1, 2, 5, 3, 5 ];
var N = arr.length;
if (check(arr, N))
document.write("Yes");
else
document.write("No");
// This code contributed by shikhasingrajput
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)