Maximice las cuerdas de longitud consecutiva posible conectando cuerdas dadas

Dada una array A[ ] de tamaño N donde cada elemento de la array representa la longitud de una cuerda, la tarea es encontrar la cantidad de cuerdas de longitud consecutiva que se pueden crear al conectar cuerdas dadas a partir de la longitud 1 .

Ejemplos:

Entrada: N = 5, A[ ] = {1, 2, 7, 1, 1}

Salida: 5 
Explicación: 
Longitud | Cuerdas 
    1 | [1] 
    2 | [1, 1] 
    3 | [1, 2] 
    4 | [1, 2, 1] 
    5 | [1, 2, 1, 1]

Entrada N = 5, A = {1, 3, 2, 4, 2} 
Salida: 12 

Enfoque: este problema se puede resolver usando el hecho de que si podemos crear cuerdas de rango [1, K] de longitud y queda una cuerda de longitud L tal que (L <= K+1) entonces podemos crear cuerdas de rango [1, K+L] agregando cuerda de longitud L a cada cuerda del rango [max(1, K-L+1), K] . Entonces, para resolver el problema, primero, ordene la array y luego recorra la array y verifique cada vez si el elemento actual es menor o igual que la longitud consecutiva máxima que hemos obtenido + 1. Si es cierto, agregue ese elemento a longitud máxima consecutiva. De lo contrario, devuelve la respuesta.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximized count
// of ropes of consecutive length
int maxConsecutiveRopes(int ropes[], int N)
{
    // Stores the maximum count
    // of ropes of consecutive length
    int curSize = 0;
 
    // Sort the ropes by their length
    sort(ropes, ropes + N);
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // If size of the current rope is less
        // than or equal to current maximum
        // possible size + 1, update the
        // range to curSize + ropes[i]
 
        if (ropes[i] <= curSize + 1) {
            curSize = curSize + ropes[i];
        }
 
        // If a rope of size (curSize + 1)
        // cannot be obtained
        else
            break;
    }
    return curSize;
}
 
// Driver Code
int main()
{
    // Input
    int N = 5;
    int ropes[] = { 1, 2, 7, 1, 1 };
 
    // Function Call
    cout << maxConsecutiveRopes(ropes, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG {
 
    // Function to find maximized count
    // of ropes of consecutive length
    static int maxConsecutiveRope(int ropes[], int N)
    {
        // Stores the maximum count
        // of ropes of consecutive length
        int curSize = 0;
 
        // Sort the ropes by their length
        Arrays.sort(ropes);
 
        // Traverse the array
        for (int i = 0; i < N; i++) {
 
            // If size of the current rope is less
            // than or equal to current maximum
            // possible size + 1, update the
            // range to curSize + ropes[i]
 
            if (ropes[i] <= curSize + 1) {
                curSize = curSize + ropes[i];
            }
 
            // If a rope of size (curSize + 1)
            // cannot be obtained
            else
                break;
        }
        return curSize;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Input
        int N = 5;
        int ropes[] = { 1, 2, 7, 1, 1 };
 
        // Function Call
        System.out.println(
            maxConsecutiveRope(ropes, N));
    }
}

# Python3 program for the above approach
 
# Function to find maximized count
# of ropes of consecutive length
def maxConsecutiveRopes(ropes, N):
 
    # Stores the maximum count
    # of ropes of consecutive length
    curSize = 0
 
    # Sort the ropes by their length
    ropes = sorted(ropes)
 
    # Traverse the array
    for i in range(N):
         
        # If size of the current rope is less
        # than or equal to current maximum
        # possible size + 1, update the
        # range to curSize + ropes[i]
        if (ropes[i] <= curSize + 1):
            curSize = curSize + ropes[i]
 
        # If a rope of size (curSize + 1)
        # cannot be obtained
        else:
            break
 
    return curSize
 
# Driver Code
if __name__ == '__main__':
     
    # Input
    N = 5
    ropes = [ 1, 2, 7, 1, 1 ]
 
    # Function Call
    print (maxConsecutiveRopes(ropes, N))
     
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to find maximized count
// of ropes of consecutive length
static int maxConsecutiveRope(int[] ropes, int N)
{
     
    // Stores the maximum count
    // of ropes of consecutive length
    int curSize = 0;
 
    // Sort the ropes by their length
    Array.Sort(ropes);
 
    // Traverse the array
    for(int i = 0; i < N; i++)
    {
         
        // If size of the current rope is less
        // than or equal to current maximum
        // possible size + 1, update the
        // range to curSize + ropes[i]
        if (ropes[i] <= curSize + 1)
        {
            curSize = curSize + ropes[i];
        }
 
        // If a rope of size (curSize + 1)
        // cannot be obtained
        else
            break;
    }
    return curSize;
}
 
// Driver code
public static void Main ()
{
     
    // Input
    int N = 5;
    int[] ropes = { 1, 2, 7, 1, 1 };
 
    // Function Call
    Console.WriteLine(maxConsecutiveRope(ropes, N));
}
}
 
// This code is contributed by souravghosh0416

<script>
// Javascript program for the above approach
 
// Function to find maximized count
// of ropes of consecutive length
function maxConsecutiveRopes(ropes, N)
{
    // Stores the maximum count
    // of ropes of consecutive length
    let curSize = 0;
 
    // Sort the ropes by their length
    ropes.sort((a, b) => a - b)
 
    // Traverse the array
    for (let i = 0; i < N; i++) {
 
        // If size of the current rope is less
        // than or equal to current maximum
        // possible size + 1, update the
        // range to curSize + ropes[i]
 
        if (ropes[i] <= curSize + 1) {
            curSize = curSize + ropes[i];
        }
 
        // If a rope of size (curSize + 1)
        // cannot be obtained
        else
            break;
    }
    return curSize;
}
 
// Driver Code
 
// Input
let N = 5;
let ropes = [ 1, 2, 7, 1, 1 ];
 
// Function Call
document.write(maxConsecutiveRopes(ropes, N));
 
// This contributed by _saurabh_jaiswal
</script>

5

Complejidad temporal: O(N)
Espacio auxiliar: O(1)