Recuento de subsecuencias con una suma en el rango [L, R] y diferencia entre el elemento máximo y mínimo al menos X

Posted on by Rudeus Greyrat

Dada una array arr[] que consiste en N enteros positivos y 3 enteros L , R y X , la tarea es encontrar el número de subsecuencias de tamaño al menos 2 con una suma en el rango [L, R] , y la diferencia entre el elemento máximo y mínimo es al menos X. (N≤15)

Ejemplos: 

Entrada: arr[] = {1 2 3}, L = 5, R = 6, X = 1
Salida: 2
Explicación: 
Hay dos subsecuencias posibles, es decir, {2, 3} y {1, 2, 3}.

Entrada: arr[] = {10, 20, 30, 25}, L = 40, R = 50, X = 10
Salida: 2

 

Enfoque: dado que N es pequeño, este problema se puede resolver utilizando máscaras de bits . Hay un total de 2 n subsecuencias posibles. Por lo tanto, cada subsecuencia se puede representar mediante una string binaria, es decir, una máscara , donde si el i-ésimo bit se establece, es decir , 1 , entonces el elemento se considera en las subsecuencias ; de lo contrario, no. Siga los pasos a continuación para resolver el problema: 

  • Iterar en el rango [0, 2 n – 1] usando la variable i y realizar los siguientes pasos:
    • Inicialice una variable, digamos, cnt como 0 y sum como 0 para almacenar la suma de los elementos seleccionados.
    • Inicialice una variable, por ejemplo, minVal como INT_MAX y maxVal como INT_MIN para almacenar el valor mínimo y el valor máximo en la subsecuencia.
    • Iterar en el rango [0, N-1] usando la variable j y realizar los siguientes pasos:
      • Si el j-ésimo bit de la i-ésima máscara está activado, aumente cnt en 1, agregue arr[j] a sum y actualice maxVal como el máximo de maxVal y a[j] y minVal como el mínimo de minVal y a[j].
    • Si cnt >= 2 y sum está en el rango [L, R] y la diferencia de maxVal y minVal es mayor que igual a X , entonces incremente ans en 1. 
  • Después de completar los pasos anteriores, imprima el valor de ans como respuesta.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of subsequences
// of the given array with a sum in range [L, R]
// and the difference between the maximum and
// minimum element is at least X
int numberofSubsequences(int a[], int L,
                         int R, int X, int n)
{
    // Initialize answer as 0
    int ans = 0;
 
    // Creating mask from [0, 2^n-1]
    for (int i = 0; i < (1 << n); i++) {
 
        // Stores the count and sum of
        // selected elements respectively
        int cnt = 0, sum = 0;
 
        // Variables to store the value of
        // Minimum and maximum element
        int minVal = INT_MAX, maxVal = INT_MIN;
 
        // Traverse the array
        for (int j = 0; j < n; j++) {
            // If the jth bit of the ith
            // mask is on
            if ((i & (1 << j))) {
 
                cnt += 1;
 
                // Add the selected element
                sum += a[j];
 
                // Update maxVal and minVal value
                maxVal = max(maxVal, a[j]);
                minVal = min(minVal, a[j]);
            }
        }
 
        // Check if the given conditions are
        // true, increment ans by 1.
        if (cnt >= 2 && sum >= L && sum <= R
            && (maxVal - minVal >= X)) {
            ans += 1;
        }
    }
    return ans;
}
 
// Driver Code
int main()
{
    // Given Input
    int a[] = { 10, 20, 30, 25 };
    int L = 40, R = 50, X = 10;
    int N = sizeof(a) / sizeof(a[0]);
 
    // Function Call
    cout << numberofSubsequences(a, L, R, X, N)
         << endl;
 
    return 0;
}

Java

// Java program for the above approach
public class GFG {
 
    // Function to find the number of subsequences
    // of the given array with a sum in range [L, R]
    // and the difference between the maximum and
    // minimum element is at least X
    static int numberofSubsequences(int a[], int L, int R,
                                    int X, int n)
    {
        // Initialize answer as 0
        int ans = 0;
 
        // Creating mask from [0, 2^n-1]
        for (int i = 0; i < (1 << n); i++) {
 
            // Stores the count and sum of
            // selected elements respectively
            int cnt = 0, sum = 0;
 
            // Variables to store the value of
            // Minimum and maximum element
            int minVal = Integer.MAX_VALUE,
                maxVal = Integer.MIN_VALUE;
 
            // Traverse the array
            for (int j = 0; j < n; j++) {
                // If the jth bit of the ith
                // mask is on
                if ((i & (1 << j)) == 0) {
 
                    cnt += 1;
 
                    // Add the selected element
                    sum += a[j];
 
                    // Update maxVal and minVal value
                    maxVal = Math.max(maxVal, a[j]);
                    minVal = Math.min(minVal, a[j]);
                }
            }
 
            // Check if the given conditions are
            // true, increment ans by 1.
            if (cnt >= 2 && sum >= L && sum <= R
                && (maxVal - minVal >= X)) {
                ans += 1;
            }
        }
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int a[] = { 10, 20, 30, 25 };
        int L = 40, R = 50, X = 10;
        int N = a.length;
 
        // Function Call
        System.out.println(
            numberofSubsequences(a, L, R, X, N));
    }
}
 
// This code is contributed by abhinavjain194

Python3

# Python3 program for the above approach
import sys
 
# Function to find the number of subsequences
# of the given array with a sum in range [L, R]
# and the difference between the maximum and
# minimum element is at least X
def numberofSubsequences(a, L, R, X, n):
     
    # Initialize answer as 0
    ans = 0
 
    # Creating mask from [0, 2^n-1]
    for i in range(0, (1 << n), 1):
         
        # Stores the count and sum of
        # selected elements respectively
        cnt = 0
        sum = 0
 
        # Variables to store the value of
        # Minimum and maximum element
        minVal = sys.maxsize
        maxVal = -sys.maxsize - 1
 
        # Traverse the array
        for j in range(n):
             
            # If the jth bit of the ith
            # mask is on
            if ((i & (1 << j))):
                cnt += 1
 
                # Add the selected element
                sum += a[j]
 
                # Update maxVal and minVal value
                maxVal = max(maxVal, a[j])
                minVal = min(minVal, a[j])
 
        # Check if the given conditions are
        # true, increment ans by 1.
        if (cnt >= 2 and sum >= L and
            sum <= R and (maxVal - minVal >= X)):
            ans += 1
             
    return ans
 
# Driver Code
if __name__ == '__main__':
     
    # Given Input
    a = [ 10, 20, 30, 25 ]
    L = 40
    R = 50
    X = 10
    N = len(a)
 
    # Function Call
    print(numberofSubsequences(a, L, R, X, N))
 
# This code is contributed by bgangwar59

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the number of subsequences
// of the given array with a sum in range [L, R]
// and the difference between the maximum and
// minimum element is at least X
static int numberofSubsequences(int[] a, int L, int R,
                                int X, int n)
{
     
    // Initialize answer as 0
    int ans = 0;
 
    // Creating mask from [0, 2^n-1]
    for(int i = 0; i < (1 << n); i++)
    {
         
        // Stores the count and sum of
        // selected elements respectively
        int cnt = 0, sum = 0;
 
        // Variables to store the value of
        // Minimum and maximum element
        int minVal = Int32.MaxValue,
            maxVal = Int32.MinValue;
 
        // Traverse the array
        for(int j = 0; j < n; j++)
        {
             
            // If the jth bit of the ith
            // mask is on
            if ((i & (1 << j)) == 0)
            {
                cnt += 1;
 
                // Add the selected element
                sum += a[j];
 
                // Update maxVal and minVal value
                maxVal = Math.Max(maxVal, a[j]);
                minVal = Math.Min(minVal, a[j]);
            }
        }
 
        // Check if the given conditions are
        // true, increment ans by 1.
        if (cnt >= 2 && sum >= L && sum <= R &&
           (maxVal - minVal >= X))
        {
            ans += 1;
        }
    }
    return ans;
}
 
// Driver Code
static public void Main()
{
    // Given input
    int[] a = { 10, 20, 30, 25 };
    int L = 40, R = 50, X = 10;
    int N = a.Length;
 
    // Function Call
    Console.Write(numberofSubsequences(a, L, R, X, N));
}
}
 
// This code is contributed by avijitmondal1998

Javascript

<script>
// Javascript program for the above approach
 
// Function to find the number of subsequences
// of the given array with a sum in range [L, R]
// and the difference between the maximum and
// minimum element is at least X
function numberofSubsequences(a, L, R, X, n)
{
 
    // Initialize answer as 0
    let ans = 0;
 
    // Creating mask from [0, 2^n-1]
    for (let i = 0; i < (1 << n); i++) {
 
        // Stores the count and sum of
        // selected elements respectively
        let cnt = 0, sum = 0;
 
        // Variables to store the value of
        // Minimum and maximum element
        let minVal = Number.MAX_SAFE_INTEGER, maxVal = Number.MIN_SAFE_INTEGER;
 
        // Traverse the array
        for (let j = 0; j < n; j++)
        {
         
            // If the jth bit of the ith
            // mask is on
            if ((i & (1 << j)))
            {
 
                cnt += 1;
 
                // Add the selected element
                sum += a[j];
 
                // Update maxVal and minVal value
                maxVal = Math.max(maxVal, a[j]);
                minVal = Math.min(minVal, a[j]);
            }
        }
 
        // Check if the given conditions are
        // true, increment ans by 1.
        if (cnt >= 2 && sum >= L && sum <= R
            && (maxVal - minVal >= X)) {
            ans += 1;
        }
    }
    return ans;
}
 
// Driver Code
 
// Given Input
let a = [10, 20, 30, 25];
let L = 40, R = 50, X = 10;
let N = a.length;
 
// Function Call
document.write(numberofSubsequences(a, L, R, X, N) + "<br>");
 
// This code is contributed by gfgking.
</script>
Producción

2

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

Publicación traducida automáticamente

Artículo escrito por aayushstar300 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *