Dada una array arr[] que consta de N enteros y dos enteros L y R , la tarea es contar el número de pares cuya suma se encuentra en el rango [L, R] .
Ejemplos:
Entrada: arr[] = {5, 1, 2}, L = 4, R = 7
Salida: 2
Explicación:
Los pares que cumplen las condiciones necesarias son los siguientes:
- (5, 1): Suma = 5 + 1 = 6, que se encuentra en el rango [4, 7].
- (5, 2): Suma = 5 + 2 = 7, que se encuentra en el rango [4, 7].
Por lo tanto, la cuenta de tales pares es 2.
Entrada: arr[] = {5, 1, 2, 4, 3}, L = 5, R = 8
Salida: 7
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los pares posibles y contar aquellos pares cuya suma se encuentra sobre el rango [L, R] . Después de verificar todos los pares, imprima el conteo total de pares.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar ordenando la array y luego realizando una búsqueda binaria para encontrar la cantidad de elementos para cada elemento de la array arr[i] de modo que la suma no exceda el rango dado. Siga los pasos para resolver el problema:
- Ordene la array arr[] en orden creciente .
- Inicialice las variables, digamos, a la derecha como N – 1 y cuente como 0 para almacenar números de pares cuya suma se encuentra en el rango [L, R] .
- Iterar hasta que la derecha sea mayor que 0 y realizar los siguientes pasos:
- Encuentre el índice inicial del elemento cuya suma con arr[right] es mayor o igual que L y guárdelo en una variable, digamos start .
- Encuentre el índice final del elemento antes de arr[right] cuya suma con arr[right] sea menor o igual que R , y luego guárdelo en una variable, digamos end .
- Si el final es mayor que el inicio , agregue (final – inicio + 1) al conteo que representa el número de elementos cuya suma con el elemento actual se encuentra sobre el rango [L, R] y luego disminuya a la derecha en 1 .
- Después de completar los pasos anteriores, imprima el valor de conteo como resultado.
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 count pairs whose
// sum lies over the range [L, R]
int countPairSum(int arr[], int L,
int R, int N)
{
// Sort the given array
sort(arr, arr + N);
int right = N - 1, count = 0;
// Iterate until right > 0
while (right > 0) {
// Starting index of element
// whose sum with arr[right] >= L
auto it1
= lower_bound(arr, arr + N,
L - arr[right]);
int start = it1 - arr;
// Ending index of element
// whose sum with arr[right] <= R
auto it2
= upper_bound(arr, arr + N,
R - arr[right]);
--it2;
int end = it2 - arr;
// Update the value of end
end = min(end, right - 1);
// Add the count of elements
// to the variable count
if (end - start >= 0) {
count += (end - start + 1);
}
right--;
}
// Return the value of count
return count;
}
// Driver Code
int main()
{
int arr[] = { 5, 1, 2, 4, 3 };
int L = 5, R = 8;
int N = sizeof(arr) / sizeof(arr[0]);
cout << countPairSum(arr, L, R, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static int lowerBound(int[] a, int low, int high, int element){
while(low < high){
int middle = low + (high - low)/2;
if(element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
static int upperBound(int[] a, int low, int high, int element){
while(low < high){
int middle = low + (high - low)/2;
if(a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
// Function to count pairs whose
// sum lies over the range [L, R]
static int countPairSum(int arr[], int L,
int R, int N)
{
// Sort the given array
Arrays.sort(arr);
int right = N - 1, count = 0;
// Iterate until right > 0
while (right > 0) {
// Starting index of element
// whose sum with arr[right] >= L
int it1
= lowerBound(arr, 0,N,
L - arr[right]);
it1++;
int start = it1 - arr[0];
// Ending index of element
// whose sum with arr[right] <= R
int it2
= upperBound(arr, 0,N,
R - arr[right]);
int end = it2 - arr[0];
// Update the value of end
end = Math.min(end, right - 1);
// Add the count of elements
// to the variable count
if (end - start >= 0) {
count += (end - start +1);
}
right--;
}
// Return the value of count
return count;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 5, 1, 2, 4, 3 };
int L = 5, R = 8;
int N = arr.length;
System.out.print(countPairSum(arr, L, R, N));
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach from bisect import bisect_left, bisect_right # Function to count pairs whose # sum lies over the range [L, R] def countPairSum(arr, L, R, N): # Sort the given array arr.sort() right = N - 1 count = 0 # Iterate until right > 0 while (right > 0): # Starting index of element # whose sum with arr[right] >= L it1 = bisect_left(arr, L - arr[right]) start = it1 # Ending index of element # whose sum with arr[right] <= R it2 = bisect_right(arr, R - arr[right]) it2 -= 1 end = it2 # Update the value of end end = min(end, right - 1) # Add the count of elements # to the variable count if (end - start >= 0): count += (end - start + 1) right -= 1 # Return the value of count return count # Driver Code if __name__ == '__main__': arr = [ 5, 1, 2, 4, 3 ] L = 5 R = 8 N = len(arr) print(countPairSum(arr, L, R, N)) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
public class GFG {
static int lowerBound(int[] a, int low, int high, int element) {
while (low < high) {
int middle = low + (high - low) / 2;
if (element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
static int upperBound(int[] a, int low, int high, int element) {
while (low < high) {
int middle = low + (high - low) / 2;
if (a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
// Function to count pairs whose
// sum lies over the range [L, R]
static int countPairSum(int []arr, int L, int R, int N)
{
// Sort the given array
Array.Sort(arr);
int right = N - 1, count = 0;
// Iterate until right > 0
while (right > 0) {
// Starting index of element
// whose sum with arr[right] >= L
int it1 = lowerBound(arr, 0, N, L - arr[right]);
it1++;
int start = it1 - arr[0];
// Ending index of element
// whose sum with arr[right] <= R
int it2 = upperBound(arr, 0, N, R - arr[right]);
int end = it2 - arr[0];
// Update the value of end
end = Math.Min(end, right - 1);
// Add the count of elements
// to the variable count
if (end - start >= 0) {
count += (end - start + 1);
}
right--;
}
// Return the value of count
return count;
}
// Driver Code
public static void Main(String[] args) {
int []arr = { 5, 1, 2, 4, 3 };
int L = 5, R = 8;
int N = arr.Length;
Console.Write(countPairSum(arr, L, R, N));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// javascript program for the above approach
function lowerBound(a , low , high , element) {
while (low < high) {
var middle = low + parseInt((high - low) / 2);
if (element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
function upperBound(a , low , high , element) {
while (low < high) {
var middle = low + parseInt((high - low) / 2);
if (a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
// Function to count pairs whose
// sum lies over the range [L, R]
function countPairSum(arr , L , R , N)
{
// Sort the given array
arr.sort((a,b)=>a-b);
var right = N - 1, count = 0;
// Iterate until right > 0
while (right > 0) {
// Starting index of element
// whose sum with arr[right] >= L
var it1 = lowerBound(arr, 0, N, L - arr[right]);
it1++;
var start = it1 - arr[0];
// Ending index of element
// whose sum with arr[right] <= R
var it2 = upperBound(arr, 0, N, R - arr[right]);
var end = it2 - arr[0];
// Update the value of end
end = Math.min(end, right - 1);
// Add the count of elements
// to the variable count
if (end - start >= 0) {
count += (end - start + 1);
}
right--;
}
// Return the value of count
return count;
}
// Driver Code
var arr = [ 5, 1, 2, 4, 3 ];
var L = 5, R = 8;
var N = arr.length;
document.write(countPairSum(arr, L, R, N));
// This code is contributed by gauravrajput1
</script>
Producción:
7
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por elitecoder y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA