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.

Methods to find the solution

Now we will explain two different methods to find the solution to the above problem.

Brute force method

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).

Efficient method

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.

Example

#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;
}

Output

Pair does not exist.

The above code description

• Declares a two-dimensional array and stores elements in it.
• Traverse the array to find if (sum - Matrix[i][j]) != hash.end().
• If the condition is met, print "Pair contains" and return from the main function.
• Otherwise, continue traversing the array and finally print "Pair does notify.".

Conclusion

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!