Dada una array de enteros ordenados y un número x, la tarea es contar pares en una array cuya suma sea menor que x.
Ejemplos:
Input : arr[] = {1, 3, 7, 9, 10, 11}
x = 7
Output : 1
There is only one pair (1, 3)
Input : arr[] = {1, 2, 3, 4, 5, 6, 7, 8}
x = 7
Output : 6
Pairs are (1, 2), (1, 3), (1, 4), (1, 5)
(2, 3) and (2, 4)
Una solución simple de este problema es ejecutar dos bucles para generar todos los pares uno por uno y verificar si la suma del par actual es menor que x o no.
Una solución eficiente de este problema es tomar el valor inicial y último del índice en la variable l y r.
1) Initialize two variables l and r to find the candidate
elements in the sorted array.
(a) l = 0
(b) r = n - 1
2) Initialize : result = 0
2) Loop while l < r.
// If current left and current
// right have sum smaller than x,
// the all elements from l+1 to r
// form a pair with current
(a) If (arr[l] + arr[r] < x)
result = result + (r - l)
(b) Else
r--;
3) Return result
A continuación se muestra la implementación de los pasos anteriores.
C++
// C++ program to count pairs in an array
// whose sum is less than given number x
#include<bits/stdc++.h>
using namespace std;
// Function to count pairs in array
// with sum less than x.
int findPairs(int arr[],int n,int x)
{
int l = 0, r = n-1;
int result = 0;
while (l < r)
{
// If current left and current
// right have sum smaller than x,
// the all elements from l+1 to r
// form a pair with current l.
if (arr[l] + arr[r] < x)
{
result += (r - l);
l++;
}
// Move to smaller value
else
r--;
}
return result;
}
// Driven code
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
int n = sizeof(arr)/sizeof(int);
int x = 7;
cout << findPairs(arr, n, x);
return 0;
}
Java
// Java program to count pairs in an array
// whose sum is less than given number x
class GFG {
// Function to count pairs in array
// with sum less than x.
static int findPairs(int arr[], int n, int x)
{
int l = 0, r = n - 1;
int result = 0;
while (l < r)
{
// If current left and current
// right have sum smaller than x,
// the all elements from l+1 to r
// form a pair with current l.
if (arr[l] + arr[r] < x)
{
result += (r - l);
l++;
}
// Move to smaller value
else
r--;
}
return result;
}
// Driver method
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
int n = arr.length;
int x = 7;
System.out.print(findPairs(arr, n, x));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to count pairs # in an array whose sum is less # than given number x # Function to count pairs in array # with sum less than x. def findPairs(arr, n, x): l = 0; r = n-1 result = 0 while (l < r): # If current left and current # right have sum smaller than x, # the all elements from l+1 to r # form a pair with current l. if (arr[l] + arr[r] < x): result += (r - l) l += 1 # Move to smaller value else: r -= 1 return result # Driver Code arr = [1, 2, 3, 4, 5, 6, 7, 8] n = len(arr) x = 7 print(findPairs(arr, n, x)) # This code is contributed by Anant Agarwal.
C#
// C# program to count pairs in
// an array whose sum is less
// than given number x
using System;
class GFG {
// Function to count pairs in array
// with sum less than x.
static int findPairs(int []arr, int n,
int x)
{
int l = 0, r = n - 1;
int result = 0;
while (l < r)
{
// If current left and current
// right have sum smaller than x,
// the all elements from l+1 to r
// form a pair with current l.
if (arr[l] + arr[r] < x)
{
result += (r - l);
l++;
}
// Move to smaller value
else
r--;
}
return result;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {1, 2, 3, 4, 5, 6, 7, 8};
int n = arr.Length;
int x = 7;
Console.Write(findPairs(arr, n, x));
}
}
// This code is contributed by parashar...
PHP
<?php
// PHP program to count pairs in an array
// whose sum is less than given number x
// Function to count pairs in array
// with sum less than x.
function findPairs($arr,$n,$x)
{
$l = 0;
$r = $n - 1;
$result = 0;
while ($l < $r)
{
// If current left and current
// right have sum smaller than x,
// the all elements from l+1 to r
// form a pair with current l.
if ($arr[$l] + $arr[$r] < $x)
{
$result += ($r - $l);
$l++;
}
// Move to smaller value
else
$r--;
}
return $result;
}
// Driver Code
$arr = array(1, 2, 3, 4, 5, 6, 7, 8);
$n = sizeof($arr) / sizeof($arr[0]);
$x = 7;
echo findPairs($arr, $n, $x);
return 0;
// This code is contributed by nitin mittal.
?>
Javascript
<script>
//javascript program to count pairs in an array
// whose sum is less than given number x
// Function to count pairs in array
// with sum less than x.
function findPairs(arr,n,x)
{
let l = 0, r = n-1;
let result = 0;
while (l < r)
{
// If current left and current
// right have sum smaller than x,
// the all elements from l+1 to r
// form a pair with current l.
if (arr[l] + arr[r] < x)
{
result += (r - l);
l++;
}
// Move to smaller value
else
r--;
}
return result;
}
let arr = [1, 2, 3, 4, 5, 6, 7, 8];
let n = arr.length;
let x = 7;
document.write(findPairs(arr,n,x));
// This code is contributed by vaibhavrabadiya117.
</script>
6
Complejidad temporal : O(n)
Espacio auxiliar : O(1)
Uso de la estructura de datos basada en políticas:
También funciona para la array sin ordenar.
C++
#include <iostream>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set \
tree<pair<int, int>, null_type, less<pair<int, int> >, \
rb_tree_tag, tree_order_statistics_node_update>
int countPair(vector<int> v, int sum)
{
int ans = 0;
ordered_set st;
int y = 0;
for (auto i = v.rbegin(); i != v.rend(); i++) {
int num = *i;
if (st.empty())
st.insert({ num, y });
else {
int left = sum - num;
ans += st.order_of_key({ left, -1 });
st.insert({ num, y });
}
y++;
}
return ans;
}
int main()
{
int n;
cin >> n;
vector<int> v{ 1, 2, 3, 4, 5, 6, 7, 8 };
int sum = 7;
cout << countPair(v, sum);
return 0;
}
6
Complejidad temporal : O(n)
Espacio auxiliar : O(n)
Extensión:
si la array no está ordenada, entonces podemos ordenar la array primero y luego aplicar el método anterior para resolver en el tiempo O (n Log n) y el espacio auxiliar requerido=O(n), donde n representa el tamaño de la array dada.
Artículos relacionados:
Contar todos los pares distintos con diferencia igual a k
Contar pares con suma dada
Este artículo es una contribución de DANISH_RAZA . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuir@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA