Dada una array arr[] de longitud N y un entero K , la tarea es encontrar la máxima longitud de la array agregando como máximo K elementos de modo que la array se convierta en una permutación de números consecutivos a partir de 1 . Una vez que se agregan K elementos, se puede insertar la suma de dos o más elementos de array.
Nota: Los elementos se pueden formar como la suma de los elementos originalmente presentes en la array o los elementos adjuntos. Pero los elementos agregados como la suma de dos o más elementos de la array no se pueden usar para generar más elementos.
Ejemplos:
Entrada: N = 3, K = 1, arr[] = {1, 2, 4}
Salida: 8
Explicación:
Elementos de array originales = {1, 2, 4} Los
elementos de array que se pueden obtener usando estos elementos son {3, 5, 6, 7}.
Inserta 8 en la array.
Ahora, todos los números que van del 9 al 15 se pueden agregar a la array.
Por lo tanto, la array se convierte en una secuencia consecutiva de 15 números.Entrada: N = 5, K=4, arr[N] = {1, 3, 10, 3, 1}
Salida: 223
Enfoque: La idea es ordenar la array arr[] en orden ascendente y luego usar el hecho de que si la suma de los elementos de la array arr[] es sum , entonces todos los elementos desde 1 hasta sum pueden formarse y si no, entonces es requerido para insertar el elemento sum+1 en la array arr[] y restar el valor de K por 1. Siga los pasos a continuación para resolver el problema:
- Ordene la array arr[].
- Inicialice el índice de la variable como 0 para mantener el índice del elemento en la array arr[] y x como 0 para almacenar la respuesta.
- Iterar en un ciclo while hasta que el índice sea menor que N y realizar los siguientes pasos:
- Si arr[index] es mayor que x , y si K es igual a 0 , entonces se rompe .
- De lo contrario, aumente el valor de x en x y reste el valor de k en 1.
- De lo contrario, agregue el valor de arr[índice] al valor de x y aumente el valor de índice en 1.
- Iterar en un ciclo while hasta que K no sea igual a 0 y realizar los siguientes pasos:
- Aumenta el valor de x por x y resta el valor de k por 1 .
- Después de realizar los pasos anteriores, imprima el valor de x-1 como respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum length // possible void findMaximumLength(int n, int k, int arr[]) { // Sort the array sort(arr, arr + n); // Initializing the variables int x = 1; int index = 0; // Iterate over the range while (index < n) { if (arr[index] > x) { // If k is 0, then no // element can be inserted if (k == 0) break; // Insert the element x = x + x; k--; } else { x += arr[index++]; } } // Insert the remaining // possible elements while (k != 0) { x = x + x; k--; } // Print the answer cout << x - 1 << endl; } // Driver Code int main() { int n = 5, k = 4; int arr[n] = { 1, 3, 10, 3, 1 }; findMaximumLength(n, k, arr); return 0; }
Java
// Java code for the above approach import java.io.*; import java.util.Arrays; class GFG { // Function to find the maximum length // possible static void findMaximumLength(int n, int k, int arr[]) { // Sort the array Arrays.sort(arr); // Initializing the variables int x = 1; int index = 0; // Iterate over the range while (index < n) { if (arr[index] > x) { // If k is 0, then no // element can be inserted if (k == 0) break; // Insert the element x = x + x; k--; } else { x += arr[index++]; } } // Insert the remaining // possible elements while (k != 0) { x = x + x; k--; } // Print the answer System.out.println(x - 1); } // Driver Code public static void main(String[] args) { int n = 5, k = 4; int arr[] = { 1, 3, 10, 3, 1 }; findMaximumLength(n, k, arr); } } // This code is contributed by Potta Lokesh
Python3
# Python code for the above approach # Function to find the maximum length # possible def findMaximumLength(n, k, arr): # Sort the array arr.sort(); # Initializing the variables x = 1; index = 0; # Iterate over the range while (index < n): if (arr[index] > x): # If k is 0, then no # element can be inserted if (k == 0): break; # Insert the element x = x + x; k-=1; else: x += arr[index]; index += 1; # Insert the remaining # possible elements while (k != 0): x = x + x; k -= 1; # Print answer print(x - 1); # Driver Code if __name__ == '__main__': n = 5; k = 4; arr = [ 1, 3, 10, 3, 1 ]; findMaximumLength(n, k, arr); # This code is contributed by 29AjayKumar
C#
// C# program for the above approach using System; class GFG{ // Function to find the maximum length // possible static void findMaximumLength(int n, int k, int []arr) { // Sort the array Array.Sort(arr); // Initializing the variables int x = 1; int index = 0; // Iterate over the range while (index < n) { if (arr[index] > x) { // If k is 0, then no // element can be inserted if (k == 0) break; // Insert the element x = x + x; k--; } else { x += arr[index++]; } } // Insert the remaining // possible elements while (k != 0) { x = x + x; k--; } // Print the answer Console.Write(x - 1); } // Driver Code public static void Main(String[] args) { int n = 5, k = 4; int []arr = { 1, 3, 10, 3, 1 }; findMaximumLength(n, k, arr); } } // This code is contributed by shivanisinghss2110
Javascript
<script> // Javascript program for the above approach // Function to find the maximum length // possible function findMaximumLength(n, k, arr) { // Sort the array arr.sort((a, b) => a - b); // Initializing the variables let x = 1; let index = 0; // Iterate over the range while (index < n) { if (arr[index] > x) { // If k is 0, then no // element can be inserted if (k == 0) break; // Insert the element x = x + x; k--; } else { x += arr[index++]; } } // Insert the remaining // possible elements while (k != 0) { x = x + x; k--; } // Print the answer document.write(x - 1); } // Driver Code let n = 5, k = 4; let arr = [1, 3, 10, 3, 1]; findMaximumLength(n, k, arr); // This code is contributed by _saurabh_jaiswal. </script>
223
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por parthagarwal1962000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA