Cuente trillizos de un rango dado que tiene la suma de dos números de un triplete igual al tercer número

Dados dos números enteros L y R , la tarea es encontrar el número de tripletes únicos cuyos valores se encuentran en el rango [L, R] , tal que la suma de dos números cualquiera sea igual al tercer número.

Ejemplos:

Entrada: L = 1, R = 3
Salida: 3
Explicación: Tres de esos tripletes que satisfacen las condiciones necesarias son (1, 1, 2), (1, 2, 3) y (2, 1, 3).

Entrada: L = 2, R = 6
Salida: 6

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los tripletes posibles en el rango [L, R] y contar esos tripletes que tienen la suma de dos números cualquiera del par igual al tercer número. Después de verificar todos los tripletes, imprima el conteo total obtenido. 
Complejidad de Tiempo: O((R – L) 3 )
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:

  • Si la diferencia entre el rango dado es menor que L , entonces no existe tal triplete que tenga la suma de dos números igual al tercer número.
  • Si la diferencia entre el rango dado es al menos L , entonces (R – L) se encuentra en el rango L y R , es decir, {L, (R – L), R} . Se puede observar que la suma de L y cualquier otro número en el rango [L, R – L] es como máximo R .
  • Por lo tanto, el número total de posibles tripletas válidas, donde el primer elemento es L viene dado por (R – L – L + 1) .
  • De manera similar, cuando el primer elemento es (L + 1) , entonces el número de tripletes es (R – L – L) , y así sucesivamente.

De las observaciones anteriores, el número total de tripletes forma un AP con los términos (R – L – L + 1), (R – L – L), (R – L – L – 1), ……… que consta de ( R – L – L + 1) número de términos. Por lo tanto, el número total de trillizos viene dado por:

\frac{N*(N + 1)}{2}
donde, N es (R – L – L + 1)

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 triplets
// from the range [L, R] having sum of two
// numbers from the triplet equal to the third number
int totalCombination(int L, int R)
{
    // Stores the total number of triplets
    int count = 0;
 
    // Find the difference of the range
    int K = R - L;
 
    // Case 1: If triplets can't
    // be formed, then return 0
    if (K < L)
        return 0;
 
    // Otherwise
    int ans = K - L;
 
    // Update the total number of triplets
    count = ((ans + 1) * (ans + 2)) / 2;
 
    // Return the count
    return count;
}
 
// Driver Code
int main()
{
    int L = 2, R = 6;
    cout << totalCombination(L, R);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
class GFG
{
 
  // Function to find the number of triplets
  // from the range [L, R] having sum of two
  // numbers from the triplet equal to the third number
  static int totalCombination(int L, int R)
  {
 
    // Stores the total number of triplets
    int count = 0;
 
    // Find the difference of the range
    int K = R - L;
 
    // Case 1: If triplets can't
    // be formed, then return 0
    if (K < L)
      return 0;
 
    // Otherwise
    int ans = K - L;
 
    // Update the total number of triplets
    count = ((ans + 1) * (ans + 2)) / 2;
 
    // Return the count
    return count;
  }
 
  // Driven Code
  public static void main(String[] args)
  {
    int L = 2, R = 6;
    System.out.print(totalCombination(L, R));
  }
}
 
// This code is contributed by susmitakundugoaldanga.

Python3

# Python3 program for the above approach
 
 
# Function to find the number of triplets
# from the range [L, R] having sum of two
# numbers from the triplet equal to the third number
def totalCombination(L, R):
   
    # Stores the total number of triplets
    count = 0
 
    # Find the difference of the range
    K = R - L
 
    # Case 1: If triplets can't
    # be formed, then return 0
    if (K < L):
        return 0
 
    # Otherwise
    ans = K - L
 
    # Update the total number of triplets
    count = ((ans + 1) * (ans + 2)) // 2
 
    # Return the count
    return count
 
# Driver Code
if __name__ == '__main__':
    L, R = 2, 6
    print (totalCombination(L, R))
 
# This code is contributed by mohit kumar 29.

C#

// C# program to implement
// the above approach
using System;
class GFG
{
   
  // Function to find the number of triplets
  // from the range [L, R] having sum of two
  // numbers from the triplet equal to the third number
  static int totalCombination(int L, int R)
  {
     
    // Stores the total number of triplets
    int count = 0;
 
    // Find the difference of the range
    int K = R - L;
 
    // Case 1: If triplets can't
    // be formed, then return 0
    if (K < L)
      return 0;
 
    // Otherwise
    int ans = K - L;
 
    // Update the total number of triplets
    count = ((ans + 1) * (ans + 2)) / 2;
 
    // Return the count
    return count;
  }
 
 
  // Driver Code
  public static void Main()
  {
    int L = 2, R = 6;
    Console.WriteLine(totalCombination(L, R));
  }
}
 
// This code is contributed by sauravghosh0416.

Javascript

<script>
    // Javascript program for the above approach
     
    // Function to find the number of triplets
    // from the range [L, R] having sum of two
    // numbers from the triplet equal to the third number
    function totalCombination(L, R)
    {
        // Stores the total number of triplets
        let count = 0;
 
        // Find the difference of the range
        let K = R - L;
 
        // Case 1: If triplets can't
        // be formed, then return 0
        if (K < L)
            return 0;
 
        // Otherwise
        let ans = K - L;
 
        // Update the total number of triplets
        count = ((ans + 1) * (ans + 2)) / 2;
 
        // Return the count
        return count;
    }
     
    let L = 2, R = 6;
    document.write(totalCombination(L, R));
 
</script>
Producción: 

6

 

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por abhijeet010304 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 *