Dada una array arr[] de tamaño N , la tarea es verificar si es posible hacer que la array no sea decreciente aplicando la operación dada como máximo una vez en cada elemento de la array. En una sola operación, se puede disminuir el elemento en uno, es decir, arr[i] = arr[i] – 1 .
Ejemplos:
Entrada: arr[] = {1, 2, 1, 2, 3}
Salida: Sí
Aplicar la operación dada en el 2º y el 4º elemento .
Ahora, la array se convierte en {1, 1, 1, 1, 3}
Entrada: arr[] = {1, 3, 1}
Salida: No
Enfoque: Procese los elementos en orden creciente y disminuya el elemento actual siempre que se pueda sin hacerlo menor que el elemento anterior. (Por lo tanto, el primer elemento siempre debe disminuirse). Si en algún momento el elemento actual es menor que el elemento anterior, no importa qué operación se realice, la respuesta es «No».
La razón por la que esta estrategia es óptima es que disminuir un número hará que sea más fácil (o al menos fácil) tratar con el siguiente elemento de la lista, ya que cualquier valor que podría haber tomado el siguiente elemento seguirá funcionando cuando el número anterior sea más bajo. y, de hecho, disminuir el número anterior amplía el rango de valores posibles para el siguiente conjunto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to make array non-decreasing
bool isPossible(int a[], int n)
{
// Take the first element
int cur = a[0];
// Perform the operation
cur--;
// Traverse the array
for (int i = 1; i < n; i++) {
// Next element
int nxt = a[i];
// If next element is greater than the
// current element then decrease
// it to increase the possibilities
if (nxt > cur)
nxt--;
// It is not possible to make the
// array non-decreasing with
// the given operation
else if (nxt < cur)
return false;
// Next element is now the current
cur = nxt;
}
// The array can be made non-decreasing
// with the given operation
return true;
}
// Driver code
int main()
{
int a[] = { 1, 2, 1, 2, 3 };
int n = sizeof(a) / sizeof(a[0]);
if (isPossible(a, n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to make array non-decreasing
static boolean isPossible(int a[], int n)
{
// Take the first element
int cur = a[0];
// Perform the operation
cur--;
// Traverse the array
for (int i = 1; i < n; i++)
{
// Next element
int nxt = a[i];
// If next element is greater than the
// current element then decrease
// it to increase the possibilities
if (nxt > cur)
nxt--;
// It is not possible to make the
// array non-decreasing with
// the given operation
else if (nxt < cur)
return false;
// Next element is now the current
cur = nxt;
}
// The array can be made non-decreasing
// with the given operation
return true;
}
// Driver code
public static void main(String []args)
{
int a[] = { 1, 2, 1, 2, 3 };
int n = a.length;
if (isPossible(a, n))
System.out.printf("Yes");
else
System.out.printf("No");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach
# Function to make array non-decreasing
def isPossible(a, n) :
# Take the first element
cur = a[0];
# Perform the operation
cur -= 1;
# Traverse the array
for i in range(1, n) :
# Next element
nxt = a[i];
# If next element is greater than the
# current element then decrease
# it to increase the possibilities
if (nxt > cur) :
nxt -= 1;
# It is not possible to make the
# array non-decreasing with
# the given operation
elif (nxt < cur) :
return False;
# Next element is now the current
cur = nxt;
# The array can be made non-decreasing
# with the given operation
return True;
# Driver code
if __name__ == "__main__" :
a = [ 1, 2, 1, 2, 3 ];
n = len(a);
if (isPossible(a, n)) :
print("Yes");
else :
print("No");
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to make array non-decreasing
static Boolean isPossible(int []a, int n)
{
// Take the first element
int cur = a[0];
// Perform the operation
cur--;
// Traverse the array
for (int i = 1; i < n; i++)
{
// Next element
int nxt = a[i];
// If next element is greater than the
// current element then decrease
// it to increase the possibilities
if (nxt > cur)
nxt--;
// It is not possible to make the
// array non-decreasing with
// the given operation
else if (nxt < cur)
return false;
// Next element is now the current
cur = nxt;
}
// The array can be made non-decreasing
// with the given operation
return true;
}
// Driver code
public static void Main(String []args)
{
int []a = { 1, 2, 1, 2, 3 };
int n = a.Length;
if (isPossible(a, n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the approach
// Function to make array non-decreasing
function isPossible(a, n)
{
// Take the first element
var cur = a[0];
// Perform the operation
cur--;
// Traverse the array
for(var i = 1; i < n; i++)
{
// Next element
var nxt = a[i];
// If next element is greater than the
// current element then decrease
// it to increase the possibilities
if (nxt > cur)
nxt--;
// It is not possible to make the
// array non-decreasing with
// the given operation
else if (nxt < cur)
return false;
// Next element is now the current
cur = nxt;
}
// The array can be made non-decreasing
// with the given operation
return true;
}
// Driver Code
var a = [ 1, 2, 1, 2, 3 ];
var n = a.length;
if (isPossible(a, n))
document.write("Yes");
else
document.write("No");
// This code is contributed by Khushboogoyal499
</script>
Yes
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA