Dada una array arr[] de enteros positivos, la tarea es encontrar si es posible hacer que esta array aumente estrictamente modificando al menos un elemento.
Ejemplos:
Entrada: arr[] = {2, 4, 8, 6, 9, 12}
Salida: Sí
Al modificar 8 a 5, la array se volverá estrictamente creciente.
es decir, {2, 4, 5, 6, 9, 12}
Entrada: arr[] = {10, 5, 2}
Salida: No
Enfoque: Para cada elemento arr[i] , si es mayor que arr[i – 1] y arr[i + 1] o es más pequeño que arr[i – 1] y arr[i + 1] entonces arr [i] necesita ser modificado.
es decir , arr[i] = (arr[i – 1] + arr[i + 1]) / 2 . Si después de la modificación, arr[i] = arr[i – 1] o arr[i] = arr[i + 1] , entonces la array no se puede hacer estrictamente creciente sin afectar a más de un solo elemento. De lo contrario, cuente todas las modificaciones, si el recuento de modificaciones al final es menor o igual a 1 , imprima «Sí» , de lo contrario, imprima «No»..
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
// Function that returns true if arr[]
// can be made strictly increasing after
// modifying at most one element
bool check(int arr[], int n)
{
// To store the number of modifications
// required to make the array
// strictly increasing
int modify = 0;
// Check whether the first element needs
// to be modify or not
if (arr[0] > arr[1]) {
arr[0] = arr[1] / 2;
modify++;
}
// Loop from 2nd element to the 2nd last element
for (int i = 1; i < n - 1; i++) {
// Check whether arr[i] needs to be modified
if ((arr[i - 1] < arr[i] && arr[i + 1] < arr[i])
|| (arr[i - 1] > arr[i] && arr[i + 1] > arr[i])) {
// Modifying arr[i]
arr[i] = (arr[i - 1] + arr[i + 1]) / 2;
// Check if arr[i] is equal to any of
// arr[i-1] or arr[i+1]
if (arr[i] == arr[i - 1] || arr[i] == arr[i + 1])
return false;
modify++;
}
}
// Check whether the last element needs
// to be modify or not
if (arr[n - 1] < arr[n - 2])
modify++;
// If more than 1 modification is required
if (modify > 1)
return false;
return true;
}
// Driver code
int main()
{
int arr[] = { 2, 4, 8, 6, 9, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
if (check(arr, n))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
Java
// Java implementation of the approach
class GFG {
// Function that returns true if arr[]
// can be made strictly increasing after
// modifying at most one element
static boolean check(int arr[], int n)
{
// To store the number of modifications
// required to make the array
// strictly increasing
int modify = 0;
// Check whether the first element needs
// to be modify or not
if (arr[0] > arr[1]) {
arr[0] = arr[1] / 2;
modify++;
}
// Loop from 2nd element to the 2nd last element
for (int i = 1; i < n - 1; i++) {
// Check whether arr[i] needs to be modified
if ((arr[i - 1] < arr[i] && arr[i + 1] < arr[i])
|| (arr[i - 1] > arr[i] && arr[i + 1] > arr[i])) {
// Modifying arr[i]
arr[i] = (arr[i - 1] + arr[i + 1]) / 2;
// Check if arr[i] is equal to any of
// arr[i-1] or arr[i+1]
if (arr[i] == arr[i - 1] || arr[i] == arr[i + 1])
return false;
modify++;
}
}
// Check whether the last element needs
// to be modify or not
if (arr[n - 1] < arr[n - 2])
modify++;
// If more than 1 modification is required
if (modify > 1)
return false;
return true;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 2, 4, 8, 6, 9, 12 };
int n = arr.length;
if (check(arr, n))
System.out.print("Yes");
else
System.out.print("No");
}
}
C#
// C# implementation of the approach
using System;
class GFG
{
// Function that returns true if arr[]
// can be made strictly increasing after
// modifying at most one element
static bool check(int []arr, int n)
{
// To store the number of modifications
// required to make the array
// strictly increasing
int modify = 0;
// Check whether the first element needs
// to be modify or not
if (arr[0] > arr[1])
{
arr[0] = arr[1] / 2;
modify++;
}
// Loop from 2nd element to the 2nd last element
for (int i = 1; i < n - 1; i++)
{
// Check whether arr[i] needs to be modified
if ((arr[i - 1] < arr[i] && arr[i + 1] < arr[i])
|| (arr[i - 1] > arr[i] && arr[i + 1] > arr[i]))
{
// Modifying arr[i]
arr[i] = (arr[i - 1] + arr[i + 1]) / 2;
// Check if arr[i] is equal to any of
// arr[i-1] or arr[i+1]
if (arr[i] == arr[i - 1] || arr[i] == arr[i + 1])
return false;
modify++;
}
}
// Check whether the last element needs
// to be modify or not
if (arr[n - 1] < arr[n - 2])
modify++;
// If more than 1 modification is required
if (modify > 1)
return false;
return true;
}
// Driver code
public static void Main()
{
int[] arr = { 2, 4, 8, 6, 9, 12 };
int n = arr.Length;
if (check(arr, n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by AnkitRai01
Python 3
# Python 3 implementation of above approach
# Function that returns true if arr[]
# can be made strictly increasing after
# modifying at most one element
def check( arr, n):
# To store the number of modifications
# required to make the array
# strictly increasing
modify = 0
# Check whether the first element needs
# to be modify or not
if (arr[0] > arr[1]) :
arr[0] = arr[1] // 2
modify+=1
# Loop from 2nd element to the 2nd last element
for i in range ( 1, n - 1):
# Check whether arr[i] needs to be modified
if ((arr[i - 1] < arr[i] and arr[i + 1] < arr[i])
or (arr[i - 1] > arr[i] and arr[i + 1] > arr[i])):
# Modifying arr[i]
arr[i] = (arr[i - 1] + arr[i + 1]) // 2
# Check if arr[i] is equal to any of
# arr[i-1] or arr[i+1]
if (arr[i] == arr[i - 1] or arr[i] == arr[i + 1]):
return False
modify+=1
# Check whether the last element needs
# to be modify or not
if (arr[n - 1] < arr[n - 2]):
modify+=1
# If more than 1 modification is required
if (modify > 1):
return False
return True
# Driver code
if __name__ == "__main__":
arr = [ 2, 4, 8, 6, 9, 12 ]
n = len(arr)
if (check(arr, n)):
print ( "Yes")
else:
print ("No")
# This code is contributed by ChitraNayal
Javascript
<script>
// Javascript implementation of the approach
// Function that returns true if arr[]
// can be made strictly increasing after
// modifying at most one element
function check(arr, n)
{
// To store the number of modifications
// required to make the array
// strictly increasing
var modify = 0;
// Check whether the first element needs
// to be modify or not
if (arr[0] > arr[1]) {
arr[0] = arr[1] / 2;
modify++;
}
// Loop from 2nd element to the 2nd last element
for (var i = 1; i < n - 1; i++) {
// Check whether arr[i] needs to be modified
if ((arr[i - 1] < arr[i] && arr[i + 1] < arr[i])
|| (arr[i - 1] > arr[i] && arr[i + 1] > arr[i])) {
// Modifying arr[i]
arr[i] = (arr[i - 1] + arr[i + 1]) / 2;
// Check if arr[i] is equal to any of
// arr[i-1] or arr[i+1]
if (arr[i] == arr[i - 1] || arr[i] == arr[i + 1])
return false;
modify++;
}
}
// Check whether the last element needs
// to be modify or not
if (arr[n - 1] < arr[n - 2])
modify++;
// If more than 1 modification is required
if (modify > 1)
return false;
return true;
}
// Driver code
var arr = [ 2, 4, 8, 6, 9, 12 ];
var n = arr.length;
if (check(arr, n))
document.write( "Yes" );
else
document.write( "No" );
// This code is contributed by noob2000.
</script>
Producción:
Yes
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sanjeev2552 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA