Dadas dos arrays ordenadas de tamaño m y n de elementos distintos. Dado un valor x . El problema es contar todos los pares de ambas arrays cuya suma sea igual a x .
Nota: El par tiene un elemento de cada array.
Ejemplos:
Input : arr1[] = {1, 3, 5, 7}
arr2[] = {2, 3, 5, 8}
x = 10
Output : 2
The pairs are:
(5, 5) and (7, 3)
Input : arr1[] = {1, 2, 3, 4, 5, 7, 11}
arr2[] = {2, 3, 4, 5, 6, 8, 12}
x = 9
Output : 5
Método 1 (enfoque ingenuo): utilizando dos bucles, seleccione elementos de ambas arrays y verifique si la suma del par es igual ax o no.
C++
// C++ implementation to count
// pairs from both sorted arrays
// whose sum is equal to a given
// value
#include <bits/stdc++.h>
using namespace std;
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value
int countPairs(int arr1[], int arr2[],
int m, int n, int x)
{
int count = 0;
// generating pairs from
// both the arrays
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
// if sum of pair is equal
// to 'x' increment count
if ((arr1[i] + arr2[j]) == x)
count++;
// required count of pairs
return count;
}
// Driver Code
int main()
{
int arr1[] = {1, 3, 5, 7};
int arr2[] = {2, 3, 5, 8};
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
int x = 10;
cout << "Count = "
<< countPairs(arr1, arr2, m, n, x);
return 0;
}
Java
// Java implementation to count pairs from
// both sorted arrays whose sum is equal
// to a given value
import java.io.*;
class GFG {
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value
static int countPairs(int []arr1,
int []arr2, int m, int n, int x)
{
int count = 0;
// generating pairs from
// both the arrays
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
// if sum of pair is equal
// to 'x' increment count
if ((arr1[i] + arr2[j]) == x)
count++;
// required count of pairs
return count;
}
// Driver Code
public static void main (String[] args)
{
int arr1[] = {1, 3, 5, 7};
int arr2[] = {2, 3, 5, 8};
int m = arr1.length;
int n = arr2.length;
int x = 10;
System.out.println( "Count = "
+ countPairs(arr1, arr2, m, n, x));
}
}
// This code is contributed by anuj_67.
Python3
# python implementation to count
# pairs from both sorted arrays
# whose sum is equal to a given
# value
# function to count all pairs from
# both the sorted arrays whose sum
# is equal to a given value
def countPairs(arr1, arr2, m, n, x):
count = 0
# generating pairs from both
# the arrays
for i in range(m):
for j in range(n):
# if sum of pair is equal
# to 'x' increment count
if arr1[i] + arr2[j] == x:
count = count + 1
# required count of pairs
return count
# Driver Program
arr1 = [1, 3, 5, 7]
arr2 = [2, 3, 5, 8]
m = len(arr1)
n = len(arr2)
x = 10
print("Count = ",
countPairs(arr1, arr2, m, n, x))
# This code is contributed by Shrikant13.
C#
// C# implementation to count pairs from
// both sorted arrays whose sum is equal
// to a given value
using System;
class GFG {
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value
static int countPairs(int []arr1,
int []arr2, int m, int n, int x)
{
int count = 0;
// generating pairs from
// both the arrays
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
// if sum of pair is equal
// to 'x' increment count
if ((arr1[i] + arr2[j]) == x)
count++;
// required count of pairs
return count;
}
// Driver Code
public static void Main ()
{
int []arr1 = {1, 3, 5, 7};
int []arr2 = {2, 3, 5, 8};
int m = arr1.Length;
int n = arr2.Length;
int x = 10;
Console.WriteLine( "Count = "
+ countPairs(arr1, arr2, m, n, x));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP implementation to count
// pairs from both sorted arrays
// whose sum is equal to a given
// value
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value
function countPairs( $arr1, $arr2,
$m, $n, $x)
{
$count = 0;
// generating pairs from
// both the arrays
for ( $i = 0; $i < $m; $i++)
for ( $j = 0; $j < $n; $j++)
// if sum of pair is equal
// to 'x' increment count
if (($arr1[$i] + $arr2[$j]) == $x)
$count++;
// required count of pairs
return $count;
}
// Driver Code
$arr1 = array(1, 3, 5, 7);
$arr2 = array(2, 3, 5, 8);
$m = count($arr1);
$n = count($arr2);
$x = 10;
echo "Count = ",
countPairs($arr1, $arr2,
$m,$n, $x);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript implementation to count
// pairs from both sorted arrays
// whose sum is equal to a given
// value
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value
function countPairs(arr1, arr2, m, n, x)
{
let count = 0;
// generating pairs from
// both the arrays
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
// if sum of pair is equal
// to 'x' increment count
if ((arr1[i] + arr2[j]) == x)
count++;
// required count of pairs
return count;
}
// Driver Code
let arr1 = [1, 3, 5, 7];
let arr2 = [2, 3, 5, 8];
let m = arr1.length;
let n = arr2.length;
let x = 10;
document.write("Count = "
+ countPairs(arr1, arr2, m, n, x));
// This code is contributed by Surbhi Tyagi.
</script>
Producción :
Count = 2
Complejidad de tiempo: O(mn)
Espacio auxiliar: O(1)
Método 2 (Búsqueda binaria): Para cada elemento arr1[i] , donde 1 <= i <= m , busque el valor (x – arr1[i]) en arr2[] . Si la búsqueda es exitosa, incremente el conteo .
C++
// C++ implementation to count
// pairs from both sorted arrays
// whose sum is equal to a given
// value
#include <bits/stdc++.h>
using namespace std;
// function to search 'value'
// in the given array 'arr[]'
// it uses binary search technique
// as 'arr[]' is sorted
bool isPresent(int arr[], int low,
int high, int value)
{
while (low <= high)
{
int mid = (low + high) / 2;
// value found
if (arr[mid] == value)
return true;
else if (arr[mid] > value)
high = mid - 1;
else
low = mid + 1;
}
// value not found
return false;
}
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value
int countPairs(int arr1[], int arr2[],
int m, int n, int x)
{
int count = 0;
for (int i = 0; i < m; i++)
{
// for each arr1[i]
int value = x - arr1[i];
// check if the 'value'
// is present in 'arr2[]'
if (isPresent(arr2, 0, n - 1, value))
count++;
}
// required count of pairs
return count;
}
// Driver Code
int main()
{
int arr1[] = {1, 3, 5, 7};
int arr2[] = {2, 3, 5, 8};
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
int x = 10;
cout << "Count = "
<< countPairs(arr1, arr2, m, n, x);
return 0;
}
Java
// Java implementation to count
// pairs from both sorted arrays
// whose sum is equal to a given
// value
import java.io.*;
class GFG {
// function to search 'value'
// in the given array 'arr[]'
// it uses binary search technique
// as 'arr[]' is sorted
static boolean isPresent(int arr[], int low,
int high, int value)
{
while (low <= high)
{
int mid = (low + high) / 2;
// value found
if (arr[mid] == value)
return true;
else if (arr[mid] > value)
high = mid - 1;
else
low = mid + 1;
}
// value not found
return false;
}
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value
static int countPairs(int arr1[], int arr2[],
int m, int n, int x)
{
int count = 0;
for (int i = 0; i < m; i++)
{
// for each arr1[i]
int value = x - arr1[i];
// check if the 'value'
// is present in 'arr2[]'
if (isPresent(arr2, 0, n - 1, value))
count++;
}
// required count of pairs
return count;
}
// Driver Code
public static void main (String[] args)
{
int arr1[] = {1, 3, 5, 7};
int arr2[] = {2, 3, 5, 8};
int m = arr1.length;
int n = arr2.length;
int x = 10;
System.out.println("Count = "
+ countPairs(arr1, arr2, m, n, x));
}
}
// This code is contributed by anuj_67.
Python 3
# Python 3 implementation to count
# pairs from both sorted arrays
# whose sum is equal to a given
# value
# function to search 'value'
# in the given array 'arr[]'
# it uses binary search technique
# as 'arr[]' is sorted
def isPresent(arr, low, high, value):
while (low <= high):
mid = (low + high) // 2
# value found
if (arr[mid] == value):
return True
elif (arr[mid] > value) :
high = mid - 1
else:
low = mid + 1
# value not found
return False
# function to count all pairs
# from both the sorted arrays
# whose sum is equal to a given
# value
def countPairs(arr1, arr2, m, n, x):
count = 0
for i in range(m):
# for each arr1[i]
value = x - arr1[i]
# check if the 'value'
# is present in 'arr2[]'
if (isPresent(arr2, 0, n - 1, value)):
count += 1
# required count of pairs
return count
# Driver Code
if __name__ == "__main__":
arr1 = [1, 3, 5, 7]
arr2 = [2, 3, 5, 8]
m = len(arr1)
n = len(arr2)
x = 10
print("Count = ",
countPairs(arr1, arr2, m, n, x))
# This code is contributed
# by ChitraNayal
C#
// C# implementation to count pairs from both
// sorted arrays whose sum is equal to a given
// value
using System;
class GFG {
// function to search 'value' in the given
// array 'arr[]' it uses binary search
// technique as 'arr[]' is sorted
static bool isPresent(int []arr, int low,
int high, int value)
{
while (low <= high)
{
int mid = (low + high) / 2;
// value found
if (arr[mid] == value)
return true;
else if (arr[mid] > value)
high = mid - 1;
else
low = mid + 1;
}
// value not found
return false;
}
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value
static int countPairs(int []arr1, int []arr2,
int m, int n, int x)
{
int count = 0;
for (int i = 0; i < m; i++)
{
// for each arr1[i]
int value = x - arr1[i];
// check if the 'value'
// is present in 'arr2[]'
if (isPresent(arr2, 0, n - 1, value))
count++;
}
// required count of pairs
return count;
}
// Driver Code
public static void Main ()
{
int []arr1 = {1, 3, 5, 7};
int []arr2 = {2, 3, 5, 8};
int m = arr1.Length;
int n = arr2.Length;
int x = 10;
Console.WriteLine("Count = "
+ countPairs(arr1, arr2, m, n, x));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP implementation to count
// pairs from both sorted arrays
// whose sum is equal to a given
// value
// function to search 'value'
// in the given array 'arr[]'
// it uses binary search technique
// as 'arr[]' is sorted
function isPresent($arr, $low,
$high, $value)
{
while ($low <= $high)
{
$mid = ($low + $high) / 2;
// value found
if ($arr[$mid] == $value)
return true;
else if ($arr[$mid] > $value)
$high = $mid - 1;
else
$low = $mid + 1;
}
// value not found
return false;
}
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value
function countPairs($arr1, $arr2,
$m, $n, $x)
{
$count = 0;
for ($i = 0; $i < $m; $i++)
{
// for each arr1[i]
$value = $x - $arr1[$i];
// check if the 'value'
// is present in 'arr2[]'
if (isPresent($arr2, 0,
$n - 1, $value))
$count++;
}
// required count of pairs
return $count;
}
// Driver Code
$arr1 = array(1, 3, 5, 7);
$arr2 = array(2, 3, 5, 8);
$m = count($arr1);
$n = count($arr2);
$x = 10;
echo "Count = "
, countPairs($arr1, $arr2, $m, $n, $x);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript implementation to count
// pairs from both sorted arrays
// whose sum is equal to a given
// value
// function to search 'value'
// in the given array 'arr[]'
// it uses binary search technique
// as 'arr[]' is sorted
function isPresent(arr,low,high,value)
{
while (low <= high)
{
let mid = Math.floor((low + high) / 2);
// value found
if (arr[mid] == value)
return true;
else if (arr[mid] > value)
high = mid - 1;
else
low = mid + 1;
}
// value not found
return false;
}
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value1
function countPairs(arr1,arr2,m,n,x)
{
let count = 0;
for (let i = 0; i < m; i++)
{
// for each arr1[i]
let value = x - arr1[i];
// check if the 'value'
// is present in 'arr2[]'
if (isPresent(arr2, 0, n - 1, value))
count++;
}
// required count of pairs
return count;
}
// Driver Code
let arr1=[1, 3, 5, 7];
let arr2=[2, 3, 5, 8];
let m=arr1.length;
let n = arr2.length;
let x = 10;
document.write("Count = "
+ countPairs(arr1, arr2, m, n, x));
// This code is contributed by avanitrachhadiya2155
</script>
Producción :
Count = 2
Complejidad de tiempo: O(mlogn), la búsqueda debe aplicarse en la array que es de mayor tamaño para reducir la complejidad de tiempo.
Espacio auxiliar: O(1)
Método 3 (hashing): la tabla hash se implementa usando unordered_set en C++ . Almacenamos todos los primeros elementos de la array en la tabla hash. Para los elementos de la segunda array, restamos cada elemento de x y verificamos el resultado en la tabla hash. Si el resultado está presente, incrementamos el conteo .
C++
// C++ implementation to count
// pairs from both sorted arrays
// whose sum is equal to a given
// value
#include <bits/stdc++.h>
using namespace std;
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value
int countPairs(int arr1[], int arr2[],
int m, int n, int x)
{
int count = 0;
unordered_set<int> us;
// insert all the elements
// of 1st array in the hash
// table(unordered_set 'us')
for (int i = 0; i < m; i++)
us.insert(arr1[i]);
// for each element of 'arr2[]
for (int j = 0; j < n; j++)
// find (x - arr2[j]) in 'us'
if (us.find(x - arr2[j]) != us.end())
count++;
// required count of pairs
return count;
}
// Driver Code
int main()
{
int arr1[] = {1, 3, 5, 7};
int arr2[] = {2, 3, 5, 8};
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
int x = 10;
cout << "Count = "
<< countPairs(arr1, arr2, m, n, x);
return 0;
}
Java
import java.util.*;
// Java implementation to count
// pairs from both sorted arrays
// whose sum is equal to a given
// value
class GFG
{
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value
static int countPairs(int arr1[], int arr2[],
int m, int n, int x)
{
int count = 0;
HashSet<Integer> us = new HashSet<Integer>();
// insert all the elements
// of 1st array in the hash
// table(unordered_set 'us')
for (int i = 0; i < m; i++)
us.add(arr1[i]);
// for each element of 'arr2[]
for (int j = 0; j < n; j++)
// find (x - arr2[j]) in 'us'
if (us.contains(x - arr2[j]))
count++;
// required count of pairs
return count;
}
// Driver Code
public static void main(String[] args)
{
int arr1[] = {1, 3, 5, 7};
int arr2[] = {2, 3, 5, 8};
int m = arr1.length;
int n = arr2.length;
int x = 10;
System.out.print("Count = "
+ countPairs(arr1, arr2, m, n, x));
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 implementation to count
# pairs from both sorted arrays
# whose sum is equal to a given value
# function to count all pairs from
# both the sorted arrays whose sum
# is equal to a given value
def countPairs(arr1, arr2, m, n, x):
count = 0
us = set()
# insert all the elements
# of 1st array in the hash
# table(unordered_set 'us')
for i in range(m):
us.add(arr1[i])
# or each element of 'arr2[]
for j in range(n):
# find (x - arr2[j]) in 'us'
if x - arr2[j] in us:
count += 1
# required count of pairs
return count
# Driver code
arr1 = [1, 3, 5, 7]
arr2 = [2, 3, 5, 8]
m = len(arr1)
n = len(arr2)
x = 10
print("Count =",
countPairs(arr1, arr2, m, n, x))
# This code is contributed by Shrikant13
C#
// C# implementation to count
// pairs from both sorted arrays
// whose sum is equal to a given
// value
using System;
using System.Collections.Generic;
class GFG
{
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value
static int countPairs(int []arr1, int []arr2,
int m, int n, int x)
{
int count = 0;
HashSet<int> us = new HashSet<int>();
// insert all the elements
// of 1st array in the hash
// table(unordered_set 'us')
for (int i = 0; i < m; i++)
us.Add(arr1[i]);
// for each element of 'arr2[]
for (int j = 0; j < n; j++)
// find (x - arr2[j]) in 'us'
if(us.Contains(x - arr2[j]))
count++;
// required count of pairs
return count;
}
// Driver Code
public static void Main(String[] args)
{
int []arr1 = {1, 3, 5, 7};
int []arr2 = {2, 3, 5, 8};
int m = arr1.Length;
int n = arr2.Length;
int x = 10;
Console.Write("Count = "
+ countPairs(arr1, arr2, m, n, x));
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation to count
// pairs from both sorted arrays
// whose sum is equal to a given
// value
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value
function countPairs(arr1, arr2, m, n, x)
{
let count = 0;
let us = new Set();
// insert all the elements
// of 1st array in the hash
// table(unordered_set 'us')
for (let i = 0; i < m; i++)
us.add(arr1[i]);
// for each element of 'arr2[]
for (let j = 0; j < n; j++)
// find (x - arr2[j]) in 'us'
if (us.has(x - arr2[j]))
count++;
// required count of pairs
return count;
}
// Driver Code
let arr1=[1, 3, 5, 7];
let arr2=[2, 3, 5, 8];
let m = arr1.length;
let n = arr2.length;
let x = 10;
document.write("Count = "
+ countPairs(arr1, arr2, m, n, x));
// This code is contributed by rag2127
</script>
Producción :
Count = 2
Complejidad de tiempo: O (m + n)
Espacio auxiliar: O (m), la tabla hash debe crearse de la array que tiene un tamaño más pequeño para reducir la complejidad del espacio.
Método 4 (Enfoque eficiente): este enfoque utiliza el concepto de dos punteros, uno para recorrer el primer arreglo de izquierda a derecha y otro para recorrer el segundo arreglo de derecha a izquierda.
Algoritmo:
countPairs(arr1, arr2, m, n, x)
Initialize l = 0, r = n - 1
Initialize count = 0
loop while l = 0
if (arr1[l] + arr2[r]) == x
l++, r--
count++
else if (arr1[l] + arr2[r]) < x
l++
else
r--
return count
C++
// C++ implementation to count
// pairs from both sorted arrays
// whose sum is equal to a given
// value
#include <bits/stdc++.h>
using namespace std;
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value
int countPairs(int arr1[], int arr2[],
int m, int n, int x)
{
int count = 0;
int l = 0, r = n - 1;
// traverse 'arr1[]' from
// left to right
// traverse 'arr2[]' from
// right to left
while (l < m && r >= 0)
{
// if this sum is equal
// to 'x', then increment 'l',
// decrement 'r' and
// increment 'count'
if ((arr1[l] + arr2[r]) == x)
{
l++; r--;
count++;
}
// if this sum is less
// than x, then increment l
else if ((arr1[l] + arr2[r]) < x)
l++;
// else decrement 'r'
else
r--;
}
// required count of pairs
return count;
}
// Driver Code
int main()
{
int arr1[] = {1, 3, 5, 7};
int arr2[] = {2, 3, 5, 8};
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
int x = 10;
cout << "Count = "
<< countPairs(arr1, arr2, m, n, x);
return 0;
}
Java
// Java implementation to count
// pairs from both sorted arrays
// whose sum is equal to a given
// value
import java.io.*;
class GFG {
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value
static int countPairs(int arr1[],
int arr2[], int m, int n, int x)
{
int count = 0;
int l = 0, r = n - 1;
// traverse 'arr1[]' from
// left to right
// traverse 'arr2[]' from
// right to left
while (l < m && r >= 0)
{
// if this sum is equal
// to 'x', then increment 'l',
// decrement 'r' and
// increment 'count'
if ((arr1[l] + arr2[r]) == x)
{
l++; r--;
count++;
}
// if this sum is less
// than x, then increment l
else if ((arr1[l] + arr2[r]) < x)
l++;
// else decrement 'r'
else
r--;
}
// required count of pairs
return count;
}
// Driver Code
public static void main (String[] args)
{
int arr1[] = {1, 3, 5, 7};
int arr2[] = {2, 3, 5, 8};
int m = arr1.length;
int n = arr2.length;
int x = 10;
System.out.println( "Count = "
+ countPairs(arr1, arr2, m, n, x));
}
}
// This code is contributed by anuj_67.
Python3
# Python 3 implementation to count
# pairs from both sorted arrays
# whose sum is equal to a given
# value
# function to count all pairs
# from both the sorted arrays
# whose sum is equal to a given
# value
def countPairs(arr1, arr2, m, n, x):
count, l, r = 0, 0, n - 1
# traverse 'arr1[]' from
# left to right
# traverse 'arr2[]' from
# right to left
while (l < m and r >= 0):
# if this sum is equal
# to 'x', then increment 'l',
# decrement 'r' and
# increment 'count'
if ((arr1[l] + arr2[r]) == x):
l += 1
r -= 1
count += 1
# if this sum is less
# than x, then increment l
elif ((arr1[l] + arr2[r]) < x):
l += 1
# else decrement 'r'
else:
r -= 1
# required count of pairs
return count
# Driver Code
if __name__ == '__main__':
arr1 = [1, 3, 5, 7]
arr2 = [2, 3, 5, 8]
m = len(arr1)
n = len(arr2)
x = 10
print("Count =",
countPairs(arr1, arr2,
m, n, x))
# This code is contributed
# by PrinciRaj19992
C#
// C# implementation to count
// pairs from both sorted arrays
// whose sum is equal to a given
// value
using System;
class GFG {
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value
static int countPairs(int []arr1,
int []arr2, int m, int n, int x)
{
int count = 0;
int l = 0, r = n - 1;
// traverse 'arr1[]' from
// left to right
// traverse 'arr2[]' from
// right to left
while (l < m && r >= 0)
{
// if this sum is equal
// to 'x', then increment 'l',
// decrement 'r' and
// increment 'count'
if ((arr1[l] + arr2[r]) == x)
{
l++; r--;
count++;
}
// if this sum is less
// than x, then increment l
else if ((arr1[l] + arr2[r]) < x)
l++;
// else decrement 'r'
else
r--;
}
// required count of pairs
return count;
}
// Driver Code
public static void Main ()
{
int []arr1 = {1, 3, 5, 7};
int []arr2 = {2, 3, 5, 8};
int m = arr1.Length;
int n = arr2.Length;
int x = 10;
Console.WriteLine( "Count = "
+ countPairs(arr1, arr2, m, n, x));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP implementation to count
// pairs from both sorted arrays
// whose sum is equal to a given
// value
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value
function countPairs( $arr1, $arr2,
$m, $n, $x)
{
$count = 0;
$l = 0; $r = $n - 1;
// traverse 'arr1[]' from
// left to right
// traverse 'arr2[]' from
// right to left
while ($l < $m and $r >= 0)
{
// if this sum is equal
// to 'x', then increment 'l',
// decrement 'r' and
// increment 'count'
if (($arr1[$l] + $arr2[$r]) == $x)
{
$l++; $r--;
$count++;
}
// if this sum is less
// than x, then increment l
else if (($arr1[$l] + $arr2[$r]) < $x)
$l++;
// else decrement 'r'
else
$r--;
}
// required count of pairs
return $count;
}
// Driver Code
$arr1 = array(1, 3, 5, 7);
$arr2 = array(2, 3, 5, 8);
$m = count($arr1);
$n = count($arr2);
$x = 10;
echo "Count = "
, countPairs($arr1, $arr2, $m, $n, $x);
// This code is contributed by anuj_67
?>
Javascript
<script>
// Javascript implementation to count
// pairs from both sorted arrays
// whose sum is equal to a given
// value
// function to count all pairs
// from both the sorted arrays
// whose sum is equal to a given
// value
function countPairs(arr1, arr2, m, n, x)
{
let count = 0;
let l = 0, r = n - 1;
// traverse 'arr1[]' from
// left to right
// traverse 'arr2[]' from
// right to left
while (l < m && r >= 0)
{
// if this sum is equal
// to 'x', then increment 'l',
// decrement 'r' and
// increment 'count'
if ((arr1[l] + arr2[r]) == x)
{
l++; r--;
count++;
}
// if this sum is less
// than x, then increment l
else if ((arr1[l] + arr2[r]) < x)
l++;
// else decrement 'r'
else
r--;
}
// required count of pairs
return count;
}
let arr1 = [1, 3, 5, 7];
let arr2 = [2, 3, 5, 8];
let m = arr1.length;
let n = arr2.length;
let x = 10;
document.write("Count = " + countPairs(arr1, arr2, m, n, x));
</script>
Producción :
Count = 2
Complejidad de tiempo: O(m + n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Ayush Jauhari . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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