Longitud del subarreglo más pequeño en el rango de 1 a N con una suma mayor que un valor dado

Dados dos números N y S , la tarea es encontrar la longitud del subarreglo más pequeño en el rango (1, N) tal que la suma de esos números elegidos sea mayor que S .

Ejemplos: 

Entrada: N = 5, S = 11 
Salida: 3 
Explicación: 
el subarreglo más pequeño con suma > 11 = {5, 4, 3}

Entrada: N = 4, S = 7 
Salida: 3 
Explicación: 
el subarreglo más pequeño con suma > 7 = {4, 3, 2} 
 

Enfoque ingenuo: un método de fuerza bruta consiste en seleccionar elementos en orden inverso hasta que la suma de todos los elementos seleccionados sea menor o igual que el número dado. 

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

// C++ implementation of the above implementation
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to return the count
// of minimum elements such that 
// the sum of those elements is > S.
int countNumber(int N, int S)
{
    int countElements = 0;
    // Initialize currentSum = 0
  
    int currSum = 0;
  
    // Loop from N to 1 to add the numbers
    // and check the condition.
    while (currSum <= S) {
        currSum += N;
        N--;
        countElements++;
    }
  
    return countElements;
}
  
// Driver code
int main()
{
    int N, S;
    N = 5;
    S = 11;
  
    int count = countNumber(N, S);
  
    cout << count << endl;
  
    return 0;
}

// Java implementation of the above implementation 
class GFG 
{
  
    // Function to return the count 
    // of minimum elements such that 
    // the sum of those elements is > S. 
    static int countNumber(int N, int S) 
    { 
        int countElements = 0; 
  
        // Initialize currentSum = 0 
        int currSum = 0; 
      
        // Loop from N to 1 to add the numbers 
        // and check the condition. 
        while (currSum <= S) 
        { 
            currSum += N; 
            N--; 
            countElements++; 
        } 
        return countElements; 
    } 
      
    // Driver code 
    public static void main (String[] args)
    { 
        int N, S; 
        N = 5; 
        S = 11; 
      
        int count = countNumber(N, S); 
      
        System.out.println(count); 
    } 
}
  
// This code is contributed by AnkitRai01

# Python implementation of the above implementation
  
# Function to return the count
# of minimum elements such that 
# the sum of those elements is > S.
def countNumber(N, S):
  
    countElements = 0;
    currentSum = 0
  
    currSum = 0;
  
    # Loop from N to 1 to add the numbers
    # and check the condition.
    while (currSum <= S) :
        currSum += N;
        N = N - 1;
        countElements=countElements + 1;
      
    return countElements;
  
# Driver code
N = 5;
S = 11;
count = countNumber(N, S);
print(count) ;
  
# This code is contributed by Shivi_Aggarwal

// C# implementation of the above implementation 
using System;
  
class GFG 
{
  
    // Function to return the count 
    // of minimum elements such that 
    // the sum of those elements is > S. 
    static int countNumber(int N, int S) 
    { 
        int countElements = 0; 
  
        // Initialize currentSum = 0 
        int currSum = 0; 
      
        // Loop from N to 1 to add the numbers 
        // and check the condition. 
        while (currSum <= S) 
        { 
            currSum += N; 
            N--; 
            countElements++; 
        } 
        return countElements; 
    } 
      
    // Driver code 
    public static void Main()
    { 
        int N, S; 
        N = 5; 
        S = 11; 
      
        int count = countNumber(N, S); 
      
        Console.WriteLine(count); 
    } 
}
  
// This code is contributed by AnkitRai01

<script>
// JavaScript implementation of the above implementation 
  
// Function to return the count 
// of minimum elements such that 
// the sum of those elements is > S. 
function countNumber(N, S) 
{ 
    let countElements = 0; 
      
    // Initialize currentSum = 0 
    let currSum = 0; 
  
    // Loop from N to 1 to add the numbers 
    // and check the condition. 
    while (currSum <= S) 
    { 
        currSum += N; 
        N--; 
        countElements++; 
    } 
    return countElements; 
} 
  
// Driver code 
    let N, S; 
    N = 5; 
    S = 11; 
    let count = countNumber(N, S); 
    document.write(count + "<br>"); 
  
// This code is contributed by Surbhi Tyagi.
</script>

3

Complejidad de tiempo: O(N)

Enfoque eficiente: la idea es utilizar el concepto de búsqueda binaria para resolver el problema. 
Del concepto de búsqueda binaria se sabe que el concepto se puede aplicar cuando se sabe que existe un orden en el problema. Es decir, para cada iteración, si se puede diferenciar con certeza que la respuesta requerida se encuentra en la primera mitad o en la segunda mitad (es decir), existe un patrón en el problema.
Por lo tanto, la búsqueda binaria se puede aplicar para el rango de la siguiente manera:

1. Inicializar start = 1 y end = N.
2. Encuentra medio = inicio + (fin – inicio) / 2.
3. Si la suma de todos los elementos desde el último hasta el medio es menor o igual a la suma dada, entonces end = mid else start = mid + 1.
4. Repita el paso 2 mientras el inicio es menor que el final.

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

// C++ implementation of the above approach.
  
#include <iostream>
using namespace std;
  
// Function to do a binary search
// on a given range.
int usingBinarySearch(int start, int end,
                      int N, int S)
{
    if (start >= end)
        return start;
    int mid = start + (end - start) / 2;
  
    // Total sum is the sum of N numbers.
    int totalSum = (N * (N + 1)) / 2;
  
    // Sum until mid
    int midSum = (mid * (mid + 1)) / 2;
  
    // If remaining sum is < the required value,
    // then the required number is in the right half
    if ((totalSum - midSum) <= S) {
  
        return usingBinarySearch(start, mid, N, S);
    }
    return usingBinarySearch(mid + 1, end, N, S);
}
  
// Driver code
int main()
{
    int N, S;
  
    N = 5;
    S = 11;
  
    cout << (N - usingBinarySearch(1, N, N, S) + 1)
         << endl;
  
    return 0;
}

// Java implementation of the above approach. 
class GFG 
{
      
    // Function to do a binary search 
    // on a given range. 
    static int usingBinarySearch(int start, int end, 
                                int N, int S) 
    { 
        if (start >= end) 
            return start; 
        int mid = start + (end - start) / 2; 
      
        // Total sum is the sum of N numbers. 
        int totalSum = (N * (N + 1)) / 2; 
      
        // Sum until mid 
        int midSum = (mid * (mid + 1)) / 2; 
      
        // If remaining sum is < the required value, 
        // then the required number is in the right half 
        if ((totalSum - midSum) <= S)
        { 
      
            return usingBinarySearch(start, mid, N, S); 
        } 
        return usingBinarySearch(mid + 1, end, N, S); 
    } 
      
    // Driver code 
    public static void main (String[] args)
    { 
        int N, S; 
      
        N = 5; 
        S = 11; 
      
        System.out.println(N - usingBinarySearch(1, N, N, S) + 1) ;
    }
}
  
// This code is contributed by AnkitRai01

# Python3 implementation of the above approach. 
  
# Function to do a binary search 
# on a given range. 
def usingBinarySearch(start, end, N, S) : 
  
    if (start >= end) :
        return start; 
          
    mid = start + (end - start) // 2; 
  
    # Total sum is the sum of N numbers. 
    totalSum = (N * (N + 1)) // 2; 
  
    # Sum until mid 
    midSum = (mid * (mid + 1)) // 2; 
  
    # If remaining sum is < the required value, 
    # then the required number is in the right half 
    if ((totalSum - midSum) <= S) :
  
        return usingBinarySearch(start, mid, N, S); 
      
    return usingBinarySearch(mid + 1, end, N, S); 
  
# Driver code 
if __name__ == "__main__" : 
  
    N = 5; 
    S = 11; 
  
    print(N - usingBinarySearch(1, N, N, S) + 1) ; 
      
# This code is contributed by AnkitRai01

// C# implementation of the above approach. 
using System;
  
class GFG 
{
      
    // Function to do a binary search 
    // on a given range. 
    static int usingBinarySearch(int start, int end, 
                                int N, int S) 
    { 
        if (start >= end) 
            return start; 
        int mid = start + (end - start) / 2; 
      
        // Total sum is the sum of N numbers. 
        int totalSum = (N * (N + 1)) / 2; 
      
        // Sum until mid 
        int midSum = (mid * (mid + 1)) / 2; 
      
        // If remaining sum is < the required value, 
        // then the required number is in the right half 
        if ((totalSum - midSum) <= S)
        { 
      
            return usingBinarySearch(start, mid, N, S); 
        } 
        return usingBinarySearch(mid + 1, end, N, S); 
    } 
      
    // Driver code 
    public static void Main()
    { 
        int N, S; 
      
        N = 5; 
        S = 11; 
      
        Console.WriteLine(N - usingBinarySearch(1, N, N, S) + 1) ;
    }
}
  
// This code is contributed by AnkitRai01

<script>
  
// Javascript implementation of the above approach.
  
// Function to do a binary search
// on a given range.
function usingBinarySearch(start, end, N, S)
{
    if (start >= end)
        return start;
          
    let mid = start + (end - start) / 2;
  
    // Total sum is the sum of N numbers.
    let totalSum = (N * (N + 1)) / 2;
  
    // Sum until mid
    let midSum = (mid * (mid + 1)) / 2;
  
    // If remaining sum is < the required value,
    // then the required number is in the right half
    if ((totalSum - midSum) <= S)
    {
        return usingBinarySearch(start, mid, N, S);
    }
    return usingBinarySearch(mid + 1, end, N, S);
}
  
// Driver code
let N, S;
N = 5;
S = 11;
  
document.write((N - usingBinarySearch(
      1, N, N, S) + 1) + "<br>");
  
// This code is contributed by Mayank Tyagi
  
</script>

3

Complejidad de tiempo: O (log N)
 

Tema relacionado: Subarrays, subsecuencias y subconjuntos en array