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