Dadas dos arrays ordenadas mat1 y mat2 de tamaño nxn 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. Las arrays se ordenan estrictamente, lo que significa que las arrays se ordenan de tal manera que todos los elementos de una fila se ordenan en orden creciente y para la fila ‘i’, donde 1 <= i <= n-1, primer elemento de la fila ‘i’ es mayor que el último elemento de la fila ‘i-1’.
Ejemplos:
Input : mat1[][] = { {1, 5, 6},
{8, 10, 11},
{15, 16, 18} }
mat2[][] = { {2, 4, 7},
{9, 10, 12},
{13, 16, 20} }
x = 21
Output : 4
The pairs are:
(1, 20), (5, 16), (8, 13) and (11, 10).
Método 1 (enfoque ingenuo): para cada elemento ele de mat1[][] busque linealmente (x – ele) en mat2[][].
C++
// C++ implementation to count pairs from two
// sorted matrices whose sum is equal to a
// given value x
#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
// function to search 'val' in mat[][]
// returns true if 'val' is present
// else false
bool valuePresent(int mat[][SIZE], int n, int val)
{
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (mat[i][j] == val)
// 'val' found
return true;
// 'val' not found
return false;
}
// function to count pairs from two sorted matrices
// whose sum is equal to a given value x
int countPairs(int mat1[][SIZE], int mat2[][SIZE],
int n, int x)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
// if value (x-mat1[i][j]) is found in mat2[][]
if (valuePresent(mat2, n, x - mat1[i][j]))
count++;
// required count of pairs
return count;
}
// Driver program to test above
int main()
{
int mat1[][SIZE] = { { 1, 5, 6 },
{ 8, 10, 11 },
{ 15, 16, 18 } };
int mat2[][SIZE] = { { 2, 4, 7 },
{ 9, 10, 12 },
{ 13, 16, 20 } };
int n = 3;
int x = 21;
cout << "Count = "
<< countPairs(mat1, mat2, n, x);
return 0;
}
Java
// java implementation to count
// pairs from twosorted matrices
// whose sum is equal to a given value
import java.io.*;
class GFG
{
int SIZE= 10;
// function to search 'val' in mat[][]
// returns true if 'val' is present
// else false
static boolean valuePresent(int mat[][], int n,
int val)
{
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (mat[i][j] == val)
// 'val' found
return true;
// 'val' not found
return false;
}
// function to count pairs from
// two sorted matrices whose sum
// is equal to a given value x
static int countPairs(int mat1[][], int mat2[][],
int n, int x)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
// if value (x-mat1[i][j]) is
// found in mat2[][]
if (valuePresent(mat2, n, x - mat1[i][j]))
count++;
}
// required count of pairs
return count;
}
// Driver program
public static void main (String[] args)
{
int mat1[][] = { { 1, 5, 6 },
{ 8, 10, 11 },
{ 15, 16, 18 } };
int mat2[][] = { { 2, 4, 7 },
{ 9, 10, 12 },
{ 13, 16, 20 } };
int n = 3;
int x = 21;
System.out.println ("Count = " +
countPairs(mat1, mat2, n, x));
}
}
// This article is contributed by vt_m
Python3
# Python3 implementation to count pairs # from two sorted matrices whose sum is # equal to a given value x # function to search 'val' in mat[][] # returns true if 'val' is present else # false def valuePresent(mat, n, val): for i in range(0, n): for j in range(0, n): if mat[i][j] == val: # 'val' found return True # 'val' not found return False # function to count pairs from two sorted # matrices whose sum is equal to a given # value x def countPairs(mat1, mat2, n, x): count = 0 for i in range(0, n): for j in range(0, n): # if value (x-mat1[i][j]) is found # in mat2[][] if valuePresent(mat2, n, x - mat1[i][j]): count += 1 # required count of pairs return count # Driver program mat1 = [[ 1, 5, 6 ], [ 8, 10, 11 ], [ 15, 16, 18 ] ] mat2 = [ [ 2, 4, 7 ], [ 9, 10, 12 ], [ 13, 16, 20 ] ] n = 3 x = 21 print( "Count = "), print(countPairs(mat1, mat2, n, x)) # This code is contributed by upendra bartwal
C#
//C# implementation to count
// pairs from twosorted matrices
// whose sum is equal to a given value
using System;
class GFG
{
// int SIZE= 10;
// function to search 'val' in mat[][]
// returns true if 'val' is present
// else false
static bool valuePresent(int[,] mat, int n,
int val)
{
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (mat[i, j] == val)
// 'val' found
return true;
// 'val' not found
return false;
}
// function to count pairs from
// two sorted matrices whose sum
// is equal to a given value x
static int countPairs(int [,]mat1, int [,]mat2,
int n, int x)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
// if value (x-mat1[i][j]) is
// found in mat2[][]
if (valuePresent(mat2, n, x - mat1[i,j]))
count++;
}
// required count of pairs
return count;
}
// Driver program
public static void Main ()
{
int [,]mat1 = { { 1, 5, 6 },
{ 8, 10, 11 },
{ 15, 16, 18 } };
int [,]mat2 = { { 2, 4, 7 },
{ 9, 10, 12 },
{ 13, 16, 20 } };
int n = 3;
int x = 21;
Console.WriteLine("Count = " +
countPairs(mat1, mat2, n, x));
}
}
// This article is contributed by vt_m
PHP
<?php
//PHP implementation to count pairs from two
// sorted matrices whose sum is equal to a
// given value x
// function to search 'val' in mat[][]
// returns true if 'val' is present
// else false
function valuePresent($mat, $n, $val)
{
for ($i = 0; $i < $n; $i++)
for ($j = 0; $j < $n; $j++)
if ($mat[$i][$j] == $val)
// 'val' found
return true;
// 'val' not found
return false;
}
// function to count pairs from two sorted matrices
// whose sum is equal to a given value x
function countPairs($mat1, $mat2, $n, $x)
{
$count = 0;
for ($i = 0; $i < $n; $i++)
for ( $j = 0; $j < $n; $j++)
// if value (x-mat1[i][j]) is found in mat2[][]
if (valuePresent($mat2, $n, $x - $mat1[$i][$j]))
$count++;
// required count of pairs
return $count;
}
// Driver program to test above
$mat1 = array(array( 1, 5, 6 ),
array( 8, 10, 11 ),
array( 15, 16, 18 ));
$mat2 = array(array( 2, 4, 7 ),
array(9, 10, 12 ),
array(13, 16, 20 ));
$n = 3;
$x = 21;
echo "Count = ",
countPairs($mat1, $mat2, $n, $x);
#This code is contributed by ajit.
?>
Javascript
<script>
// Javascript implementation to count
// pairs from twosorted matrices
// whose sum is equal to a given value
let SIZE = 10;
// Function to search 'val' in mat[][]
// returns true if 'val' is present
// else false
function valuePresent(mat, n, val)
{
for(let i = 0; i < n; i++)
for(let j = 0; j < n; j++)
if (mat[i][j] == val)
// 'val' found
return true;
// 'val' not found
return false;
}
// Function to count pairs from
// two sorted matrices whose sum
// is equal to a given value x
function countPairs(mat1, mat2, n, x)
{
let count = 0;
for(let i = 0; i < n; i++)
for(let j = 0; j < n; j++)
{
// If value (x-mat1[i][j]) is
// found in mat2[][]
if (valuePresent(mat2, n, x - mat1[i][j]))
count++;
}
// Required count of pairs
return count;
}
// Driver code
let mat1 = [ [ 1, 5, 6 ],
[ 8, 10, 11 ],
[ 15, 16, 18 ] ];
let mat2 = [ [ 2, 4, 7 ],
[ 9, 10, 12 ],
[ 13, 16, 20 ] ];
let n = 3;
let x = 21;
document.write("Count = " +
countPairs(mat1, mat2, n, x));
// This code is contributed by divyeshrabadiya07
</script>
Producción:
Count = 4
Complejidad Temporal: O(n 4 ).
Espacio Auxiliar: O(1).
Método 2 (búsqueda binaria): como la array está estrictamente ordenada, utilice el concepto de técnica de búsqueda binaria. Para cada elemento ele de mat1[][], aplique la técnica de búsqueda binaria en los elementos de la primera columna de mat2[][] para encontrar el número de índice de fila del elemento más grande menor que igual a (x – ele) . Que sea fila_no . Si no existe tal fila, entonces no se puede formar ningún par con el elemento ele . De lo contrario, aplique el concepto de técnica de búsqueda binaria para encontrar el valor (x – ele) en la fila representada por row_no en mat2[][]. Si se encuentra el valor, entonces incremente el conteo .
C++
// C++ implementation to count pairs from two
// sorted matrices whose sum is equal to a given
// value x
#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
// function returns the row index no of largest
// element smaller than equal to 'x' in first
// column of mat[][]. If no such element exists
// then it returns -1.
int binarySearchOnRow(int mat[SIZE][SIZE],
int l, int h, int x)
{
while (l <= h) {
int mid = (l + h) / 2;
// if 'x' is greater than or equal to mat[mid][0],
// then search in mat[mid+1...h][0]
if (mat[mid][0] <= x)
l = mid + 1;
// else search in mat[l...mid-1][0]
else
h = mid - 1;
}
// required row index number
return h;
}
// function to search 'val' in mat[row][]
bool binarySearchOnCol(int mat[][SIZE], int l, int h,
int val, int row)
{
while (l <= h) {
int mid = (l + h) / 2;
// 'val' found
if (mat[row][mid] == val)
return true;
// search in mat[row][mid+1...h]
else if (mat[row][mid] < val)
l = mid + 1;
// search in mat[row][l...mid-1]
else
h = mid - 1;
}
// 'val' not found
return false;
}
// function to search 'val' in mat[][]
// returns true if 'val' is present
// else false
bool searchValue(int mat[][SIZE],
int n, int val)
{
// to get the row index number of the largest element
// smaller than equal to 'val' in mat[][]
int row_no = binarySearchOnRow(mat, 0, n - 1, val);
// if no such row exists, then
// 'val' is not present
if (row_no == -1)
return false;
// to search 'val' in mat[row_no][]
return binarySearchOnCol(mat, 0, n - 1, val, row_no);
}
// function to count pairs from two sorted matrices
// whose sum is equal to a given value x
int countPairs(int mat1[][SIZE], int mat2[][SIZE],
int n, int x)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
// if value (x-mat1[i][j]) is found in mat2[][]
if (searchValue(mat2, n, x - mat1[i][j]))
count++;
// required count of pairs
return count;
}
// Driver program to test above
int main()
{
int mat1[][SIZE] = { { 1, 5, 6 },
{ 8, 10, 11 },
{ 15, 16, 18 } };
int mat2[][SIZE] = { { 2, 4, 7 },
{ 9, 10, 12 },
{ 13, 16, 20 } };
int n = 3;
int x = 21;
cout << "Count = "
<< countPairs(mat1, mat2, n, x);
return 0;
}
Java
// Java implementation to count
// pairs from two sorted matrices
// whose sum is equal to a given
// value x
import java.io.*;
class GFG {
int SIZE= 10;
// function returns the row index no of largest
// element smaller than equal to 'x' in first
// column of mat[][]. If no such element exists
// then it returns -1.
static int binarySearchOnRow(int mat[][], int l,
int h, int x)
{
while (l <= h)
{
int mid = (l + h) / 2;
// if 'x' is greater than or
// equal to mat[mid][0], then
// search in mat[mid+1...h][0]
if (mat[mid][0] <= x)
l = mid + 1;
// else search in mat[l...mid-1][0]
else
h = mid - 1;
}
// required row index number
return h;
}
// function to search 'val' in mat[row][]
static boolean binarySearchOnCol(int mat[][], int l, int h,
int val, int row)
{
while (l <= h)
{
int mid = (l + h) / 2;
// 'val' found
if (mat[row][mid] == val)
return true;
// search in mat[row][mid+1...h]
else if (mat[row][mid] < val)
l = mid + 1;
// search in mat[row][l...mid-1]
else
h = mid - 1;
}
// 'val' not found
return false;
}
// function to search 'val' in mat[][]
// returns true if 'val' is present
// else false
static boolean searchValue(int mat[][],
int n, int val)
{
// to get the row index number
// of the largest element smaller
// than equal to 'val' in mat[][]
int row_no = binarySearchOnRow(mat, 0, n - 1, val);
// if no such row exists, then
// 'val' is not present
if (row_no == -1)
return false;
// to search 'val' in mat[row_no][]
return binarySearchOnCol(mat, 0, n - 1, val, row_no);
}
// function to count pairs from
// two sorted matrices whose sum
// is equal to a given value x
static int countPairs(int mat1[][], int mat2[][],
int n, int x)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
// if value (x-mat1[i][j]) is found in mat2[][]
if (searchValue(mat2, n, x - mat1[i][j]))
count++;
}
// required count of pairs
return count;
}
// Driver program
public static void main (String[] args)
{
int mat1[][] = { { 1, 5, 6 },
{ 8, 10, 11 },
{ 15, 16, 18 } };
int mat2[][] = { { 2, 4, 7 },
{ 9, 10, 12 },
{ 13, 16, 20 } };
int n = 3;
int x = 21;
System.out.println ( "Count = " +
countPairs(mat1, mat2, n, x));
}
}
// This code is contributed by vt_m
Python3
# Python 3 implementation to count pairs
# from two sorted matrices whose sum is
# equal to a given value x
SIZE = 10
# function returns the row index no of
# largest element smaller than equal
# to 'x' in first column of mat[][].
# If no such element exists then it returns -1.
def binarySearchOnRow(mat, l, h, x):
while (l <= h):
mid = int((l + h) / 2)
# if 'x' is greater than or equal
# to mat[mid][0], then search in
# mat[mid+1...h][0]
if (mat[mid][0] <= x):
l = mid + 1
# else search in mat[l...mid-1][0]
else:
h = mid - 1
# required row index number
return h
# function to search 'val' in mat[row][]
def binarySearchOnCol(mat, l, h, val, row):
while (l <= h):
mid = int((l + h) / 2)
# 'val' found
if (mat[row][mid] == val):
return True
# search in mat[row][mid+1...h]
elif (mat[row][mid] < val):
l = mid + 1
# search in mat[row][l...mid-1]
else:
h = mid - 1
# 'val' not found
return False
# function to search 'val' in mat[][]
# returns true if 'val' is present
# else false
def searchValue(mat, n, val):
# to get the row index number of the
# largest element smaller than equal
# to 'val' in mat[][]
row_no = binarySearchOnRow(mat, 0, n - 1, val)
# if no such row exists, then
# 'val' is not present
if (row_no == -1):
return False
# to search 'val' in mat[row_no][]
return binarySearchOnCol(mat, 0, n - 1,
val, row_no)
# function to count pairs from two sorted matrices
# whose sum is equal to a given value x
def countPairs(mat1, mat2, n, x):
count = 0
for i in range(n):
for j in range(n):
# if value (x-mat1[i][j]) is
# found in mat2[][]
if (searchValue(mat2, n, x - mat1[i][j])):
count += 1
# required count of pairs
return count
# Driver Code
if __name__ == '__main__':
mat1 = [[1, 5, 6],
[8, 10,11],
[15, 16, 18]]
mat2 = [[2, 4, 7],
[9, 10, 12],
[13, 16, 20]]
n = 3
x = 21
print("Count =", countPairs(mat1, mat2, n, x))
# This code is contributed by
# Shashank_Sharma
C#
// C# implementation to count
// pairs from two sorted matrices
// whose sum is equal to a given
// value x
using System;
class GFG
{
//int SIZE= 10;
// function returns the row index no of largest
// element smaller than equal to 'x' in first
// column of mat[][]. If no such element exists
// then it returns -1.
static int binarySearchOnRow(int [,]mat, int l,
int h, int x)
{
while (l <= h)
{
int mid = (l + h) / 2;
// if 'x' is greater than or
// equal to mat[mid][0], then
// search in mat[mid+1...h][0]
if (mat[mid,0] <= x)
l = mid + 1;
// else search in mat[l...mid-1][0]
else
h = mid - 1;
}
// required row index number
return h;
}
// function to search 'val' in mat[row][]
static bool binarySearchOnCol(int [,]mat, int l, int h,
int val, int row)
{
while (l <= h)
{
int mid = (l + h) / 2;
// 'val' found
if (mat[row,mid] == val)
return true;
// search in mat[row][mid+1...h]
else if (mat[row,mid] < val)
l = mid + 1;
// search in mat[row][l...mid-1]
else
h = mid - 1;
}
// 'val' not found
return false;
}
// function to search 'val' in mat[][]
// returns true if 'val' is present
// else false
static bool searchValue(int [,]mat,
int n, int val)
{
// to get the row index number
// of the largest element smaller
// than equal to 'val' in mat[][]
int row_no = binarySearchOnRow(mat, 0, n - 1, val);
// if no such row exists, then
// 'val' is not present
if (row_no == -1)
return false;
// to search 'val' in mat[row_no][]
return binarySearchOnCol(mat, 0, n - 1, val, row_no);
}
// function to count pairs from
// two sorted matrices whose sum
// is equal to a given value x
static int countPairs(int [,]mat1, int [,]mat2,
int n, int x)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
// if value (x-mat1[i][j]) is found in mat2[][]
if (searchValue(mat2, n, x - mat1[i,j]))
count++;
}
// required count of pairs
return count;
}
// Driver program
public static void Main ()
{
int [,]mat1 = { { 1, 5, 6 },
{ 8, 10, 11 },
{ 15, 16, 18 } };
int [,]mat2 = { { 2, 4, 7 },
{ 9, 10, 12 },
{ 13, 16, 20 } };
int n = 3;
int x = 21;
Console.WriteLine ( "Count = " +
countPairs(mat1, mat2, n, x));
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP implementation to count pairs
// from two sorted matrices whose sum
// is equal to a given value x
// function returns the row index no.
// of largest element smaller than
// equal to 'x' in first column of
// mat[][]. If no such element exists
// then it returns -1.
function binarySearchOnRow($mat, $l,
$h, $x)
{
while ($l <= $h)
{
$mid = ($l + $h) / 2;
// if 'x' is greater than or
// equal to mat[mid][0], then
// search in mat[mid+1...h][0]
if ($mat[$mid][0] <= $x)
$l = $mid + 1;
// else search in mat[l...mid-1][0]
else
$h = $mid - 1;
}
// required row index number
return $h;
}
// function to search 'val' in mat[row][]
function binarySearchOnCol($mat, $l, $h,
$val, $row)
{
while ($l <= $h)
{
$mid = ($l + $h) / 2;
// 'val' found
if ($mat[$row][$mid] == $val)
return true;
// search in mat[row][mid+1...h]
else if ($mat[$row][$mid] < $val)
$l = $mid + 1;
// search in mat[row][l...mid-1]
else
$h = $mid - 1;
}
// 'val' not found
return false;
}
// function to search 'val' in mat[][]
// returns true if 'val' is present
// else false
function searchValue($mat,$n, $val)
{
// to get the row index number of the
// largest element smaller than equal
// to 'val' in mat[][]
$row_no = binarySearchOnRow($mat, 0,
$n - 1, $val);
// if no such row exists, then
// 'val' is not present
if ($row_no == -1)
return false;
// to search 'val' in mat[row_no][]
return binarySearchOnCol($mat, 0, $n - 1,
$val, $row_no);
}
// function to count pairs from two
// sorted matrices whose sum is equal
// to a given value x
function countPairs($mat1, $mat2, $n, $x)
{
$count = 0;
for ($i = 0; $i < $n; $i++)
for ($j = 0; $j < $n; $j++)
// if value (x-mat1[i][j]) is
// found in mat2[][]
if (searchValue($mat2, $n,
$x - $mat1[$i][$j]))
$count++;
// required count of pairs
return $count;
}
// Driver Code
$mat1 = array(array(1, 5, 6 ),
array(8, 10, 11 ),
array(15, 16, 18 ));
$mat2 = array(array(2, 4, 7 ),
array(9, 10, 12 ),
array(13, 16, 20 ));
$n = 3;
$x = 21;
echo "Count = ",
countPairs($mat1, $mat2,
$n, $x);
// This code is contributed by ajit.
?>
Javascript
<script>
// Javascript implementation to count
// pairs from two sorted matrices
// whose sum is equal to a given
// value x
//int SIZE= 10;
// function returns the row index no of largest
// element smaller than equal to 'x' in first
// column of mat[][]. If no such element exists
// then it returns -1.
function binarySearchOnRow(mat, l, h, x)
{
while (l <= h)
{
var mid = parseInt((l + h) / 2);
// if 'x' is greater than or
// equal to mat[mid][0], then
// search in mat[mid+1...h][0]
if (mat[mid][0] <= x)
l = mid + 1;
// else search in mat[l...mid-1][0]
else
h = mid - 1;
}
// required row index number
return h;
}
// function to search 'val' in mat[row][]
function binarySearchOnCol(mat, l, h, val, row)
{
while (l <= h)
{
var mid = parseInt((l + h) / 2);
// 'val' found
if (mat[row][mid] == val)
return true;
// search in mat[row][mid+1...h]
else if (mat[row][mid] < val)
l = mid + 1;
// search in mat[row][l...mid-1]
else
h = mid - 1;
}
// 'val' not found
return false;
}
// function to search 'val' in mat[][]
// returns true if 'val' is present
// else false
function searchValue(mat, n, val)
{
// to get the row index number
// of the largest element smaller
// than equal to 'val' in mat[][]
var row_no = binarySearchOnRow(mat, 0, n - 1, val);
// if no such row exists, then
// 'val' is not present
if (row_no == -1)
return false;
// to search 'val' in mat[row_no][]
return binarySearchOnCol(mat, 0, n - 1, val, row_no);
}
// function to count pairs from
// two sorted matrices whose sum
// is equal to a given value x
function countPairs(mat1, mat2, n, x)
{
var count = 0;
for (var i = 0; i < n; i++)
for (var j = 0; j < n; j++)
{
// if value (x-mat1[i][j]) is found in mat2[][]
if (searchValue(mat2, n, x - mat1[i][j]))
count++;
}
// required count of pairs
return count;
}
// Driver program
var mat1 = [ [ 1, 5, 6 ],
[ 8, 10, 11 ],
[ 15, 16, 18 ] ];
var mat2 = [ [ 2, 4, 7 ],
[ 9, 10, 12 ],
[ 13, 16, 20 ] ];
var n = 3;
var x = 21;
document.write( "Count = " +
countPairs(mat1, mat2, n, x));
</script>
Producción:
Count = 4
Tiempo Complejidad: (n 2 log 2 n).
Espacio Auxiliar: O(1).
Método 3 (Hashing): Cree una tabla hash e inserte todos los elementos de mat2[][] en ella. Ahora, para cada elemento ele de mat1[][], busque (x – ele) en la tabla hash.
C++
// C++ implementation to count pairs from two
// sorted matrices whose sum is equal to a
// given value x
#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
// function to count pairs from two sorted matrices
// whose sum is equal to a given value x
int countPairs(int mat1[][SIZE], int mat2[][SIZE],
int n, int x)
{
int count = 0;
// unordered_set 'us' implemented as hash table
unordered_set<int> us;
// insert all the elements of mat2[][] in 'us'
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
us.insert(mat2[i][j]);
// for each element of mat1[][]
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
// if (x-mat1[i][j]) is in 'us'
if (us.find(x - mat1[i][j]) != us.end())
count++;
// required count of pairs
return count;
}
// Driver program to test above
int main()
{
int mat1[][SIZE] = { { 1, 5, 6 },
{ 8, 10, 11 },
{ 15, 16, 18 } };
int mat2[][SIZE] = { { 2, 4, 7 },
{ 9, 10, 12 },
{ 13, 16, 20 } };
int n = 3;
int x = 21;
cout << "Count = "
<< countPairs(mat1, mat2, n, x);
return 0;
}
Java
import java.util.*;
// Java implementation to count pairs from two
// sorted matrices whose sum is equal to a
// given value x
class GFG
{
// Java
static int SIZE = 10;
// function to count pairs from two sorted matrices
// whose sum is equal to a given value x
static int countPairs(int mat1[][], int mat2[][],
int n, int x)
{
int count = 0;
// unordered_set 'us' implemented as hash table
HashSet<Integer> us = new HashSet<>();
// insert all the elements of mat2[][] in 'us'
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
us.add(mat2[i][j]);
}
}
// for each element of mat1[][]
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++) // if (x-mat1[i][j]) is in 'us'
{
if (us.contains(x - mat1[i][j]))
{
count++;
}
}
}
// required count of pairs
return count;
}
// Driver code
public static void main(String[] args)
{
int mat1[][] = {{1, 5, 6},
{8, 10, 11},
{15, 16, 18}};
int mat2[][] = {{2, 4, 7},
{9, 10, 12},
{13, 16, 20}};
int n = 3;
int x = 21;
System.out.println("Count = "
+ countPairs(mat1, mat2, n, x));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python implementation to count pairs from two
# sorted matrices whose sum is equal to a
# given value x
SIZE = 10
# function to count pairs from two sorted matrices
# whose sum is equal to a given value x
def countPairs(mat1, mat2, n, x):
count = 0
# unordered_set 'us' implemented as hash table
us = set()
# insert all the elements of mat2[][] in 'us'
for i in range(n):
for j in range(n):
us.add(mat2[i][j])
# for each element of mat1[][]
for i in range(n):
for j in range(n):
# if (x-mat1[i][j]) is in 'us'
if (x - mat1[i][j]) in us:
count += 1
# required count of pairs
return count
# Driver code
mat1 = [[1, 5, 6],[8, 10, 11],[ 15, 16, 18]]
mat2 = [[2, 4, 7],[9, 10, 12],[ 13, 16, 20]]
n = 3
x = 21
print("Count =",countPairs(mat1, mat2, n, x))
# This code is contributed by shubhamsingh10
C#
// C# implementation to count pairs from two
// sorted matrices whose sum is equal to a
// given value x
using System;
using System.Collections.Generic;
class GFG
{
// C#
static int SIZE = 10;
// function to count pairs from two sorted matrices
// whose sum is equal to a given value x
static int countPairs(int [,]mat1, int [,]mat2,
int n, int x)
{
int count = 0;
// unordered_set 'us' implemented as hash table
HashSet<int> us = new HashSet<int>();
// insert all the elements of mat2[,] in 'us'
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
us.Add(mat2[i,j]);
}
}
// for each element of mat1[,]
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++) // if (x-mat1[i,j]) is in 'us'
{
if (us.Contains(x - mat1[i,j]))
{
count++;
}
}
}
// required count of pairs
return count;
}
// Driver code
public static void Main(String[] args)
{
int [,]mat1 = {{1, 5, 6},
{8, 10, 11},
{15, 16, 18}};
int [,]mat2 = {{2, 4, 7},
{9, 10, 12},
{13, 16, 20}};
int n = 3;
int x = 21;
Console.WriteLine("Count = "
+ countPairs(mat1, mat2, n, x));
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation to count pairs from two
// sorted matrices whose sum is equal to a
// given value x
var SIZE = 10;
// function to count pairs from two sorted matrices
// whose sum is equal to a given value x
function countPairs(mat1, mat2, n, x)
{
var count = 0;
// unordered_set 'us' implemented as hash table
var us = new Set();
// insert all the elements of mat2[][] in 'us'
for (var i = 0; i < n; i++)
for (var j = 0; j < n; j++)
us.add(mat2[i][j]);
// for each element of mat1[][]
for (var i = 0; i < n; i++)
for (var j = 0; j < n; j++)
// if (x-mat1[i][j]) is in 'us'
if (us.has(x - mat1[i][j]))
count++;
// required count of pairs
return count;
}
// Driver program to test above
var mat1 = [ [ 1, 5, 6 ],
[ 8, 10, 11 ],
[ 15, 16, 18 ] ];
var mat2 = [ [ 2, 4, 7 ],
[ 9, 10, 12 ],
[ 13, 16, 20 ] ];
var n = 3;
var x = 21;
document.write( "Count = "
+ countPairs(mat1, mat2, n, x));
</script>
Producción:
Count = 4
Complejidad temporal: O(n 2 ).
Espacio Auxiliar: O(n 2 ).
Método 4 (Enfoque eficiente): desde el elemento superior izquierdo, atravesar mat1[][] en dirección hacia adelante (es decir, desde la fila superior hasta la última, cada fila se recorre de izquierda a derecha) y desde el elemento inferior derecho, atravesar mat2 [][] en dirección hacia atrás (es decir, desde la fila inferior hasta la primera, cada fila se recorre de derecha a izquierda). Para cada elemento e1 de mat1[][] y e2 de mat2[][] encontrado, calcule val = (e1 + e2). Si val == x, incrementa la cuenta . De lo contrario, si val es menor que x, muévase al siguiente elemento de mat1[][] en la dirección de avance. De lo contrario, muévase al siguiente elemento de mat2[][] en dirección hacia atrás. Continúe este proceso hasta que cualquiera de las dos arrays se atraviese por completo.
C++
// C++ implementation to count pairs from two
// sorted matrices whose sum is equal to a
// given value x
#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
// function to count pairs from two sorted matrices
// whose sum is equal to a given value x
int countPairs(int mat1[][SIZE], int mat2[][SIZE],
int n, int x)
{
// 'r1' and 'c1' for pointing current element
// of mat1[][]
// 'r2' and 'c2' for pointing current element
// of mat2[][]
int r1 = 0, c1 = 0;
int r2 = n - 1, c2 = n - 1;
// while there are more elements
// in both the matrices
int count = 0;
while ((r1 < n) && (r2 >= -1)) {
int val = mat1[r1][c1] + mat2[r2][c2];
// if true
if (val == x) {
// increment 'count'
count++;
// move mat1[][] column 'c1' to right
// move mat2[][] column 'c2' to left
c1++;
c2--;
}
// if true, move mat1[][] column 'c1' to right
else if (val < x)
c1++;
// else move mat2[][] column 'c2' to left
else
c2--;
// if 'c1' crosses right boundary
if (c1 == n) {
// reset 'c1'
c1 = 0;
// increment row 'r1'
r1++;
}
// if 'c2' crosses left boundary
if (c2 == -1) {
// reset 'c2'
c2 = n - 1;
// decrement row 'r2'
r2--;
}
}
// required count of pairs
return count;
}
// Driver program to test above
int main()
{
int mat1[][SIZE] = { { 1, 5, 6 },
{ 8, 10, 11 },
{ 15, 16, 18 } };
int mat2[][SIZE] = { { 2, 4, 7 },
{ 9, 10, 12 },
{ 13, 16, 20 } };
int n = 3;
int x = 21;
cout << "Count = "
<< countPairs(mat1, mat2, n, x);
return 0;
}
Java
// java implementation to count
// pairs from two sorted
// matrices whose sum is
// equal to agiven value x
import java.io.*;
class GFG
{
int SIZE = 10;
// function to count pairs from
// two sorted matrices whose sum
// is equal to a given value x
static int countPairs(int mat1[][], int mat2[][],
int n, int x)
{
// 'r1' and 'c1' for pointing current
// element of mat1[][]
// 'r2' and 'c2' for pointing current
// element of mat2[][]
int r1 = 0, c1 = 0;
int r2 = n - 1, c2 = n - 1;
// while there are more elements
// in both the matrices
int count = 0;
while ((r1 < n) && (r2 >= 0))
{
int val = mat1[r1][c1] + mat2[r2][c2];
// if true
if (val == x) {
// increment 'count'
count++;
// move mat1[][] column 'c1' to right
// move mat2[][] column 'c2' to left
c1++;
c2--;
}
// if true, move mat1[][]
// column 'c1' to right
else if (val < x)
c1++;
// else move mat2[][] column
// 'c2' to left
else
c2--;
// if 'c1' crosses right boundary
if (c1 == n) {
// reset 'c1'
c1 = 0;
// increment row 'r1'
r1++;
}
// if 'c2' crosses left boundary
if (c2 == -1) {
// reset 'c2'
c2 = n - 1;
// decrement row 'r2'
r2--;
}
}
// required count of pairs
return count;
}
// Driver code
public static void main (String[] args)
{
int mat1[][] = { { 1, 5, 6 },
{ 8, 10, 11 },
{ 15, 16, 18 } };
int mat2[][] = { { 2, 4, 7 },
{ 9, 10, 12 },
{ 13, 16, 20 } };
int n = 3;
int x = 21;
System.out.println ( "Count = " +
countPairs(mat1, mat2, n, x));
}
}
// This article is contributed by vt_m
Python3
# Python implementation to count pairs from two
# sorted matrices whose sum is equal to a
# given value x
SIZE = 10
# function to count pairs from two sorted matrices
# whose sum is equal to a given value x
def countPairs(mat1, mat2, n, x):
# 'r1' and 'c1' for pointing current element
# of mat1[][]
# 'r2' and 'c2' for pointing current element
# of mat2[][]
r1 = 0
c1 = 0
r2 = n - 1
c2 = n - 1
# while there are more elements
# in both the matrices
count = 0
while ((r1 < n) and (r2 >= -1)):
val = mat1[r1][c1] + mat2[r2][c2]
# if true
if (val == x):
# increment 'count'
count += 1
# move mat1[][] column 'c1' to right
# move mat2[][] column 'c2' to left
c1 += 1
c2 -= 1
# if true, move mat1[][] column 'c1' to right
elif (val < x):
c1 += 1
# else move mat2[][] column 'c2' to left
else:
c2 -= 1
# if 'c1' crosses right boundary
if (c1 == n):
# reset 'c1'
c1 = 0
# increment row 'r1'
r1 += 1
# if 'c2' crosses left boundary
if (c2 == -1):
# reset 'c2'
c2 = n - 1
# decrement row 'r2'
r2 -= 1
# required count of pairs
return count
# Driver program to test above
mat1 = [ [1, 5, 6] ,[8, 10, 11 ],[15, 16, 18 ]]
mat2 = [[2, 4, 7],[ 9, 10, 12],[13, 16, 20]]
n = 3
x = 21
print("Count =",countPairs(mat1, mat2, n, x))
# This code is contributed by shubhamsingh10
C#
// C# implementation to count pairs
// from two sorted matrices whose
// sum is equal to a given value x
using System;
class GFG {
// function to count pairs from
// two sorted matrices whose sum
// is equal to a given value x
static int countPairs(int [,]mat1,
int [,]mat2, int n, int x)
{
// 'r1' and 'c1' for pointing
// current element of mat1[][]
// 'r2' and 'c2' for pointing
// current element of mat2[][]
int r1 = 0, c1 = 0;
int r2 = n - 1, c2 = n - 1;
// while there are more elements
// in both the matrices
int count = 0;
while ((r1 < n) && (r2 >= -1))
{
int val = mat1[r1,c1]
+ mat2[r2,c2];
// if true
if (val == x) {
// increment 'count'
count++;
// move mat1[][] column
// 'c1' to right
// move mat2[][] column
// 'c2' to left
c1++;
c2--;
}
// if true, move mat1[][]
// column 'c1' to right
else if (val < x)
c1++;
// else move mat2[][] column
// 'c2' to left
else
c2--;
// if 'c1' crosses right
// boundary
if (c1 == n) {
// reset 'c1'
c1 = 0;
// increment row 'r1'
r1++;
}
// if 'c2' crosses left
// boundary
if (c2 == -1) {
// reset 'c2'
c2 = n - 1;
// decrement row 'r2'
r2--;
}
}
// required count of pairs
return count;
}
// Driver code
public static void Main ()
{
int [,]mat1 = { { 1, 5, 6 },
{ 8, 10, 11 },
{ 15, 16, 18 } };
int [,]mat2 = { { 2, 4, 7 },
{ 9, 10, 12 },
{ 13, 16, 20 } };
int n = 3;
int x = 21;
Console.Write ( "Count = " +
countPairs(mat1, mat2, n, x));
}
}
// This code is contributed by
// nitin mittal
PHP
<?php
// PHP implementation to count pairs
// from two sorted matrices whose sum
// is equal to a given value x
// function to count pairs from two
// sorted matrices whose sum is equal
// to a given value x
function countPairs(&$mat1, &$mat2, $n, $x)
{
// 'r1' and 'c1' for pointing
// current element of mat1[][]
// 'r2' and 'c2' for pointing
// current element of mat2[][]
$r1 = 0;
$c1 = 0;
$r2 = $n - 1;
$c2 = $n - 1;
// while there are more elements
// in both the matrices
$count = 0;
while (($r1 < $n) && ($r2 >= -1))
{
$val = $mat1[$r1][$c1] +
$mat2[$r2][$c2];
// if true
if ($val == $x)
{
// increment 'count'
$count++;
// move mat1[][] column 'c1' to right
// move mat2[][] column 'c2' to left
$c1++;
$c2--;
}
// if true, move mat1[][]
// column 'c1' to right
else if ($val < $x)
$c1++;
// else move mat2[][] column
// 'c2' to left
else
$c2--;
// if 'c1' crosses right boundary
if ($c1 == $n)
{
// reset 'c1'
$c1 = 0;
// increment row 'r1'
$r1++;
}
// if 'c2' crosses left boundary
if ($c2 == -1)
{
// reset 'c2'
$c2 = $n - 1;
// decrement row 'r2'
$r2--;
}
}
// required count of pairs
return $count;
}
// Driver Code
$mat1 = array(array(1, 5, 6 ),
array(8, 10, 11 ),
array(15, 16, 18 ));
$mat2 = array(array(2, 4, 7),
array(9, 10, 12),
array(13, 16, 20 ));
$n = 3;
$x = 21;
echo ("Count = ");
echo countPairs($mat1, $mat2, $n, $x);
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript implementation to count
// pairs from two sorted
// matrices whose sum is
// equal to agiven value x
let SIZE = 10;
// Function to count pairs from
// two sorted matrices whose sum
// is equal to a given value x
function countPairs(mat1, mat2, n, x)
{
// 'r1' and 'c1' for pointing current
// element of mat1[][]
// 'r2' and 'c2' for pointing current
// element of mat2[][]
let r1 = 0, c1 = 0;
let r2 = n - 1, c2 = n - 1;
// While there are more elements
// in both the matrices
let count = 0;
while ((r1 < n) && (r2 >= 0))
{
let val = mat1[r1][c1] + mat2[r2][c2];
// If true
if (val == x)
{
// Increment 'count'
count++;
// Move mat1[][] column 'c1' to right
// move mat2[][] column 'c2' to left
c1++;
c2--;
}
// If true, move mat1[][]
// column 'c1' to right
else if (val < x)
c1++;
// Else move mat2[][] column
// 'c2' to left
else
c2--;
// If 'c1' crosses right boundary
if (c1 == n)
{
// Reset 'c1'
c1 = 0;
// Increment row 'r1'
r1++;
}
// If 'c2' crosses left boundary
if (c2 == -1)
{
// Reset 'c2'
c2 = n - 1;
// Decrement row 'r2'
r2--;
}
}
// Required count of pairs
return count;
}
// Driver Code
let mat1 = [ [ 1, 5, 6 ],
[ 8, 10, 11 ],
[ 15, 16, 18 ] ];
let mat2 = [ [ 2, 4, 7 ],
[ 9, 10, 12 ],
[ 13, 16, 20 ] ];
let n = 3;
let x = 21;
document.write("Count = " +
countPairs(mat1, mat2, n, x));
// This code is contributed by mukesh07
</script>
Producción:
Count = 4
Complejidad Temporal: O(n 2 ).
Espacio Auxiliar: O(1).
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA