Count pairs from two sorted matrices with given sum
Given two sorted matrices mat1 and mat2 of size n x n of distinct elements. Given a value x. The problem is to count all pairs from both matrices whose sum is equal to x.
Note: The pair has an element from each matrix. Matrices are strictly sorted which means that matrices are sorted in a way such that all elements in a row are sorted in increasing order and for row ‘i’, where 1 <= i <= n-1, first element of row ‘i’ is greater than the last element of row ‘i-1’.
Examples:
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).
Method 1 (Naive Approach): For each element ele of mat1[][] linearly search (x – ele) in mat2[][].
// 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 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
//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
<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>
<?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.
?>
# 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
Output:
Count = 4
Time Complexity: O(n4).
Auxiliary Space: O(1).
Method 2 (Binary Search): As matrix is strictly sorted, use the concept of binary search technique. For each element ele of mat1[][] apply the binary search technique on the elements of the first column of mat2[][] to find the row index number of the largest element smaller than equal to (x – ele). Let it be row_no. If no such row exists then no pair can be formed with element ele. Else apply the concept of binary search technique to find the value (x – ele) in the row represented by row_no in mat2[][]. If value found then increment count.
// 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 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
// 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
<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>
<?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.
?>
# 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
Output:
Count = 4
Time Complexity: (n2log2n).
Auxiliary Space: O(1).
Method 3 (Hashing): Create a hash table and insert all the elements of mat2[][] in it. Now for each element ele of mat1[][] find (x – ele) in the hash table.
// 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;
}
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 */
// 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
<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>
# 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
Output:
Count = 4
Time complexity: O(n2).
Auxiliary Space: O(n2).
Method 4 (Efficient Approach): From the top leftmost element traverse mat1[][] in forward direction (i.e., from the topmost row up to last, each row is being traversed from left to right) and from the bottom rightmost element traverse mat2[][] in backward direction (i.e, from the bottom row up to first, each row is being traversed from right to left). For each element e1 of mat1[][] and e2 of mat2[][] encountered, calculate val = (e1 + e2). If val == x, increment count. Else if val is less than x, move to next element of mat1[][] in forward direction. Else move to next element of mat2[][] in backward direction. Continue this process until either of the two matrices gets completely traversed.
// 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 >= 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 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 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
// 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 >= 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 ()
{
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
// 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
<?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 >= 0))
{
$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
?>
# 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 >= 0)):
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
Output:
Count = 4
Time Complexity: O(n2).
Auxiliary Space: O(1).