Home > Article > Backend Development > Written in C++, find a pair of numbers in a matrix with a given sum
In this article, we will discuss the program to find pairs with a given sum in a given matrix. For example -
Input : matrix[n][m] = { { 4, 6, 4, 65 }, { 56, 1, 12, 32 }, { 4, 5, 6, 44 }, { 13, 9, 11, 25 } }, SUM = 20 Output : Pair exists. Explanation : Sum = 20 is equal to the sum of numbers 9 and 11 which exists in the matrix. Input : matrix[n][m] = { { 5, 7, 3, 45 }, { 63, 5, 3, 7 }, { 11, 6, 9, 5 }, { 8, 6, 14, 15 } }, SUM = 13 Output : Pair does not exist. Explanation : No pair exists in the matrix whose sum is equal to 7.
Now we will explain two different methods to find the solution to the above problem.
Consider each pair in the given matrix, check if the sum of the pair is equal to the given SUM, if so, print "Pair isn't"; otherwise, Prints "Pairing does not exist". Applying this method is very simple, but it increases the time complexity to O((N*M)2).
This program can store all matrix elements by using hash, then traverse the matrix and check whether the differences of [SUM & (index element)] are equal. If so, print "Exist" and exit the program. If it is NO, "does not exist" after traversing print.
#include <bits/stdc++.h> using namespace std; #define n 4 #define m 4 int main() { int matrix[n][m] = { { 5,7, 3,45 }, { 63, 5, 3, 7 }, { 11, 6, 9, 5 }, { 8, 6, 14, 15 } }; int sum = 7; unordered_set<int> hash; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (hash.find(sum - matrix[i][j]) != hash.end()) { cout << "Pair exists." << endl; return 0; } else { hash.insert(matrix[i][j]); } } } cout << "Pair does not exist." << endl; return 0; }
Pair does not exist.
In this article, we discussed finding pairs or 2D arrays with a given sum in a matrix; we discussed both brute force and efficient ways to solve this problem . We discussed a C program to solve this problem. However, we can write this program in any other language like C, Java, Python, etc. We hope this article was helpful to you.
The above is the detailed content of Written in C++, find a pair of numbers in a matrix with a given sum. For more information, please follow other related articles on the PHP Chinese website!