Dada una array arr[] de tamaño N que consta de enteros no negativos. En un movimiento , el elemento de índice i-ésimo de la array se reduce en 1 y el índice (i+1) se incrementa en 1. La tarea es verificar si existe alguna posibilidad de hacer que la array dada sea estrictamente creciente (que solo contenga números enteros no negativos). ) haciendo cualquier número de movimientos.
Ejemplos:
Entrada: arr[3] = [1, 2, 3]
Salida: Sí
Explicación: La array ya está ordenada en orden estrictamente creciente.Entrada: arr[2] = [2, 0]
Salida: Sí
Explicación : Considere i = 0 para el primer movimiento arr[0] = 2-1 = 1, arr[1] = 0 + 1 = 1. Ahora la array se convierte en [1, 1].
En el segundo movimiento considere i = 0. Así que ahora arr[0] = 1 – 1 = 0, arr[1] = 1 + 1 = 2.
La array final se convierte en arr[2] = [0, 2], que es estrictamente creciente .Entrada: arr[3] = [0, 1, 0]
Salida: No
Explicación : Esta array no se puede hacer estrictamente creciente que contenga solo números enteros no negativos mediante la realización de cualquier número de movimientos.
Enfoque: El problema se puede resolver usando la siguiente observación matemática.
- Dado que todos los elementos de la array no son negativos, el orden estrictamente creciente mínimo de una array de tamaño N puede ser: 0, 1, 2, 3. . . (N-1) .
- Entonces, la suma mínima (min_sum) de los primeros i elementos (hasta el (it) índice) de cualquier array es min_sum = (i*(i-1))/2.
- Por lo tanto, la suma de los primeros i elementos de la array dada (cur_sum) debe satisfacer la condición cur_sum ≥ min_sum .
- Si la condición no se cumple , entonces no es posible hacer que la array dada sea estrictamente creciente. Considere el siguiente ejemplo
Ilustración 1:
arr[] = 4 5 1 2 3
min_sum = 0 1 3 6 10
sum(arr) = 4 9 10 12 15Como esta array satisface la condición para cada i, es posible convertir esta array en una array estrictamente creciente
Ilustración 2:
array[] = 2 3 1 0 2
min_sum = 0 1 3 6 10
suma(array) = 2 5 6 6 8Aquí, en el índice 4, la suma de la array no satisface la condición de tener una suma mínima de 10. Por lo tanto, no es posible cambiar la array a una estrictamente creciente.
Siga los pasos mencionados a continuación para implementar el concepto:
- Atraviese de index = 0 a index = N – 1 , y para cada i verifique si la suma hasta eso es mayor o igual a (i*(i+1))/2 .
- Si se cumple la condición, entonces la array se puede hacer estrictamente creciente. De lo contrario , no se puede hacer estrictamente creciente.
Siga la siguiente implementación para el enfoque anterior:
C++
// C++ code to check if the given array
// can be made strictly increasing
#include <bits/stdc++.h>
using namespace std;
// Function to check if
// the array can be made strictly increasing
void CheckStrictlyIncreasing(int arr[],
int N)
{
// variable to store sum till current
// index element
int cur_sum = 0;
bool possible = true;
for (int index = 0;
index < N; index++) {
cur_sum += arr[index];
// Sum of 0, 1, ...(i)th element
int req_sum = (index * (index + 1)) / 2;
// Check if valid or not
if (req_sum > cur_sum) {
possible = false;
break;
}
}
// If can be made strictly increasing
if (possible)
cout << "Yes";
else
cout << "No";
}
// Driver code
int main()
{
int arr[3] = { 1, 2, 3 };
int N = 3;
CheckStrictlyIncreasing(arr, N);
return 0;
}
Java
// Java code to check if the given array
// can be made strictly increasing
import java.util.*;
class GFG{
// Function to check if
// the array can be made strictly increasing
static void CheckStrictlyIncreasing(int arr[],
int N)
{
// variable to store sum till current
// index element
int cur_sum = 0;
boolean possible = true;
for (int index = 0;
index < N; index++) {
cur_sum += arr[index];
// Sum of 0, 1, ...(i)th element
int req_sum = (index * (index + 1)) / 2;
// Check if valid or not
if (req_sum > cur_sum) {
possible = false;
break;
}
}
// If can be made strictly increasing
if (possible)
System.out.print("Yes");
else
System.out.print("No");
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3 };
int N = 3;
CheckStrictlyIncreasing(arr, N);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python 3 code to check if the given array
# can be made strictly increasing
# Function to check if
# the array can be made strictly increasing
def CheckStrictlyIncreasing(arr,
N):
# variable to store sum till current
# index element
cur_sum = 0
possible = True
for index in range(N):
cur_sum += arr[index]
# Sum of 0, 1, ...(i)th element
req_sum = (index * (index + 1)) // 2
# Check if valid or not
if (req_sum > cur_sum):
possible = False
break
# If can be made strictly increasing
if (possible):
print("Yes")
else:
print("No")
# Driver code
if __name__ == "__main__":
arr = [1, 2, 3]
N = 3
CheckStrictlyIncreasing(arr, N)
# This code is contributed by ukasp.
C#
// C# code to check if the given array
// can be made strictly increasing
using System;
class GFG{
// Function to check if the array can
// be made strictly increasing
static void CheckStrictlyIncreasing(int []arr,
int N)
{
// Variable to store sum till current
// index element
int cur_sum = 0;
bool possible = true;
for(int index = 0;
index < N; index++)
{
cur_sum += arr[index];
// Sum of 0, 1, ...(i)th element
int req_sum = (index * (index + 1)) / 2;
// Check if valid or not
if (req_sum > cur_sum)
{
possible = false;
break;
}
}
// If can be made strictly increasing
if (possible)
Console.Write("Yes");
else
Console.Write("No");
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3 };
int N = 3;
CheckStrictlyIncreasing(arr, N);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript code for the above approach
// Function to check if
// the array can be made strictly increasing
function CheckStrictlyIncreasing(arr, N)
{
// variable to store sum till current
// index element
let cur_sum = 0;
let possible = true;
for (let index = 0;
index < N; index++) {
cur_sum += arr[index];
// Sum of 0, 1, ...(i)th element
let req_sum = (index * (index + 1)) / 2;
// Check if valid or not
if (req_sum > cur_sum) {
possible = false;
break;
}
}
// If can be made strictly increasing
if (possible)
document.write("Yes");
else
document.write("No");
}
// Driver code
let arr = [1, 2, 3];
let N = 3;
CheckStrictlyIncreasing(arr, N);
// This code is contributed by Potta Lokesh
</script>
Yes
Complejidad de tiempo: O(N)
Complejidad de espacio: O(1)