Dada una array arr[] que consta de N enteros positivos, la tarea es verificar si la array dada arr[] se puede hacer estrictamente creciente de modo que para cualquier índice i del rango [1, N – 1] , si (arr[ i – 1] – (i – 1)) es al menos 0 , luego se suma a arr[i] y se resta de arr[i – 1] . Si es posible hacer que la array sea estrictamente creciente, imprima Yes . De lo contrario , imprima No.
Ejemplos:
Entrada: arr[] = {1, 5, 2, 7, 6}
Salida: Sí
Explicación:
Considere las siguientes operaciones:
- Al elegir el índice 1 , el valor de arr[i – 1] – (i – 1) es 1, que es al menos 0. Sumar 1 a arr[1] y restarlo de arr[0], modifica la array a { 0, 6, 2, 7, 6}.
- Al elegir el índice 2 , el valor de arr[i – 1] – (i – 1) es 5, que es al menos 0. Al agregar 5 a arr[2] y restarlo de arr[1], se modifica la array a { 0, 1, 7, 7, 6}.
- Al elegir el índice 3 , el valor de arr[i – 1] – (i – 1) es 5, que es al menos 0. Sumar 6 a arr[3] y restarlo de arr[2], modifica la array a { 0, 1, 2, 12, 6}.
- Al elegir el índice 4 , el valor de arr[i – 1] – (i – 1) es 9, que es al menos 0. Sumar 9 a arr[4] y restarlo de arr[3], modifica la array a {0 , 1, 2, 3, 15}.
Después de las operaciones anteriores, la array se vuelve estrictamente creciente.
Entrada: arr[] = {0, 1, 0}
Salida: No
Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso . Siga los pasos a continuación para resolver el problema
- Recorra la array dada usando la variable i en el rango [1, N – 1] y realice los siguientes pasos:
- Si arr[i – 1] es al menos (i – 1) , realice los siguientes pasos:
- Almacene el valor de arr[i] – arr[i – 1] en una variable, digamos P .
- Actualice arr[i – 1] como arr[i – 1] – P .
- Actualice arr[i] como arr[i] + P .
- Si arr[i – 1] es al menos (i – 1) , realice los siguientes pasos:
- Después de completar los pasos anteriores, si la array arr[] está ordenada , imprima «Sí» . De lo contrario, escriba «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 check if an array
// can be made strictly increasing
void check(int arr[], int n)
{
// Traverse the given array arr[]
for (int i = 1; i < n; i++) {
if (arr[i - 1] >= (i - 1)) {
// Update the value of p,
// arr[i], and arr[i - 1]
int p = arr[i - 1] - (i - 1);
arr[i] += p;
arr[i - 1] -= p;
}
}
// Traverse the given array
for (int i = 1; i < n; i++) {
// Check if the array arr[] is
// strictly increasing or not
if (arr[i] <= arr[i - 1]) {
cout << "No";
return;
}
}
// Otherwise, array is increasing
// order, print Yes
cout << "Yes";
}
// Driver Code
int main()
{
int arr[] = { 1, 5, 2, 7, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
check(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to check if an array
// can be made strictly increasing
static void check(int arr[], int n)
{
// Traverse the given array arr[]
for(int i = 1; i < n; i++)
{
if (arr[i - 1] >= (i - 1))
{
// Update the value of p,
// arr[i], and arr[i - 1]
int p = arr[i - 1] - (i - 1);
arr[i] += p;
arr[i - 1] -= p;
}
}
// Traverse the given array
for(int i = 1; i < n; i++)
{
// Check if the array arr[] is
// strictly increasing or not
if (arr[i] <= arr[i - 1])
{
System.out.println("No");
return;
}
}
// Otherwise, array is increasing
// order, print Yes
System.out.println("Yes");
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 5, 2, 7, 6 };
int N = arr.length;
check(arr, N);
}
}
// This code is contributed by Dharanendra L V.
Python3
# Python3 program for the above approach
# Function to check if an array
# can be made strictly increasing
def check(arr, n):
# Traverse the given array arr[]
for i in range(1, n):
if (arr[i - 1] >= (i - 1)):
# Update the value of p,
# arr[i], and arr[i - 1]
p = arr[i - 1] - (i - 1)
arr[i] += p
arr[i - 1] -= p
# Traverse the given array
for i in range(1, n):
# Check if the array arr[] is
# strictly increasing or not
if (arr[i] <= arr[i - 1]):
print ("No")
return
# Otherwise, array is increasing
# order, prYes
print ("Yes")
# Driver Code
if __name__ == '__main__':
arr = [1, 5, 2, 7, 6]
N = len(arr)
check(arr, N)
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check if an array
// can be made strictly increasing
static void check(int []arr, int n)
{
// Traverse the given array arr[]
for(int i = 1; i < n; i++)
{
if (arr[i - 1] >= (i - 1))
{
// Update the value of p,
// arr[i], and arr[i - 1]
int p = arr[i - 1] - (i - 1);
arr[i] += p;
arr[i - 1] -= p;
}
}
// Traverse the given array
for(int i = 1; i < n; i++)
{
// Check if the array arr[] is
// strictly increasing or not
if (arr[i] <= arr[i - 1])
{
Console.Write("No");
return;
}
}
// Otherwise, array is increasing
// order, print Yes
Console.Write("Yes");
}
// Driver Code
public static void Main()
{
int []arr = { 1, 5, 2, 7, 6 };
int N = arr.Length;
check(arr, N);
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// Javascript program for the above approach
// Function to check if an array
// can be made strictly increasing
function check(arr, n)
{
// Traverse the given array arr
for(var i = 1; i < n; i++)
{
if (arr[i - 1] >= (i - 1))
{
// Update the value of p,
// arr[i], and arr[i - 1]
var p = arr[i - 1] - (i - 1);
arr[i] += p;
arr[i - 1] -= p;
}
}
// Traverse the given array
for(var i = 1; i < n; i++)
{
// Check if the array arr is
// strictly increasing or not
if (arr[i] <= arr[i - 1])
{
document.write("No");
return;
}
}
// Otherwise, array is increasing
// order, print Yes
document.write("Yes");
}
// Driver Code
var arr = [ 1, 5, 2, 7, 6 ];
var N = arr.length;
check(arr, N);
// This code is contributed by 29AjayKumar
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Akshita207 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA