Dada una array arr[] que consta de N enteros, reorganice la array de modo que satisfaga las siguientes condiciones:
- arr[0] debe ser 1 .
- La diferencia entre elementos de array adyacentes no debe exceder 1 , es decir, arr[i] – arr[i-1] ≤ 1 para todo 1 ≤ i < N.
Las operaciones permitidas son las siguientes:
- Reorganizar los elementos de cualquier manera.
- Reducir cualquier elemento a cualquier número ≥ 1 .
La tarea es encontrar el valor máximo posible que se puede colocar en el último índice de la array.
Ejemplos:
Entrada: arr[] = {3, 1, 3, 4}
Salida: 4
Explicación:
Restar 1 del primer elemento modifica la array a {2, 1, 3, 4}.
Al intercambiar los dos primeros elementos, la array se modifica a {1, 2, 3, 4}.
Por lo tanto, el valor máximo colocado en el último índice es 4.
Entrada: arr[] = {1, 1, 1, 1}
Salida: 1
Enfoque:
para resolver el problema dado, ordene la array dada y equilíbrela de acuerdo con la condición dada, comenzando de izquierda a derecha. Siga los pasos a continuación para resolver el problema:
- Ordene la array en orden ascendente.
- Si el primer elemento no es 1 , conviértalo en 1 .
- Recorra la array sobre los índices [1, N – 1) y verifique si cada elemento adyacente tiene una diferencia de ≤ 1 .
- De lo contrario, disminuya el valor hasta que la diferencia sea ≤ 1 .
- Devuelve el último elemento de la array.
A continuación se muestra la implementación del problema anterior:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum possible value // that can be placed at the last index int maximizeFinalElement(int arr[], int n) { // Sort array in ascending order sort(arr, arr + n); // If the first element // is not equal to 1 if (arr[0] != 1) arr[0] = 1; // Traverse the array to make // difference between adjacent // elements <=1 for (int i = 1; i < n; i++) { if (arr[i] - arr[i - 1] > 1) { arr[i] = arr[i - 1] + 1; } } return arr[n - 1]; } // Driver Code int main() { int n = 4; int arr[] = { 3, 1, 3, 4 }; int max = maximizeFinalElement(arr, n); cout << max; return 0; }
Java
// Java program to implement // the above approach import java.io.*; import java.util.*; class GFG{ // Function to find the maximum possible value // that can be placed at the last index public static int maximizeFinalElement(int arr[], int n) { // Sort the array elements // in ascending order Arrays.sort(arr); // If the first element is // is not equal to 1 if (arr[0] != 1) arr[0] = 1; // Traverse the array to make // difference between adjacent // elements <=1 for(int i = 1; i < n; i++) { if (arr[i] - arr[i - 1] > 1) { arr[i] = arr[i - 1] + 1; } } return arr[n - 1]; } // Driver Code public static void main (String[] args) { int n = 4; int arr[] = { 3, 1, 3, 4 }; int max = maximizeFinalElement(arr, n); System.out.print(max); } }
Python3
# Python3 program to implement # the above approach # Function to find the maximum possible value # that can be placed at the last index def maximizeFinalElement(arr, n): # Sort the array elements # in ascending order arr.sort(); # If the first element is # is not equal to 1 if (arr[0] != 1): arr[0] = 1; # Traverse the array to make # difference between adjacent # elements <=1 for i in range(1, n): if (arr[i] - arr[i - 1] > 1): arr[i] = arr[i - 1] + 1; return arr[n - 1]; # Driver Code if __name__ == '__main__': n = 4; arr = [3, 1, 3, 4]; max = maximizeFinalElement(arr, n); print(max); # This code is contributed by Princi Singh
C#
// C# Program to implement // the above approach using System; class GFG{ // Function to find the maximum possible value // that can be placed at the last index public static int maximizeFinalElement(int []arr, int n) { // Sort the array elements // in ascending order Array.Sort(arr); // If the first element is // is not equal to 1 if (arr[0] != 1) arr[0] = 1; // Traverse the array to make // difference between adjacent // elements <=1 for (int i = 1; i < n; i++) { if (arr[i] - arr[i - 1] > 1) { arr[i] = arr[i - 1] + 1; } } return arr[n - 1]; } // Driver Code public static void Main(String[] args) { int n = 4; int []arr = { 3, 1, 3, 4 }; int max = maximizeFinalElement(arr, n); Console.WriteLine(max); } } // This code is contributed by sapnasingh4991
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the maximum possible value // that can be placed at the last index function maximizeFinalElement(arr, n) { // Sort array in ascending order arr.sort((a, b) => a - b); // If the first element // is not equal to 1 if (arr[0] != 1) arr[0] = 1; // Traverse the array to make // difference between adjacent // elements <=1 for (let i = 1; i < n; i++) { if (arr[i] - arr[i - 1] > 1) { arr[i] = arr[i - 1] + 1; } } return arr[n - 1]; } // Driver Code let n = 4; let arr = [ 3, 1, 3, 4 ]; let max = maximizeFinalElement(arr, n); document.write(max); // This code is contributed by Surbhi Tyagi. </script>
4
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)