Maximize product of a matrix by repeatedly multiplying pairs of adjacent cells with -1
Given a matrix mat[][] of dimensions NxN consisting of integers, the task is to find the maximum product of elements of the matrix mat[][] possible repeatedly multiplying pairs of adjacent cells by -1.
Note: The value of any matrix element can be changed by -1 at most once.
Examples:
Input: arr[][] = {{1, -2}, {2, -3}}
Output: 12
Explanation:
Multiply arr[0][1] and arr[1][1] by -1. Therefore, product of the matrix = = 1 * 2 * 2 * 3 = 12.Input: arr[][] = {{2, 2}, {-3, 1}};
Output: 216
Approach: The given problem can be solved based on the following observations:
- If the count of negative numbers present in the matrix is even and the count of 0s in the matrix is 1, then change that 0 to 1 and then print the product of all elements in the matrix as the result. Otherwise, print 0 as the result.
- Otherwise, change the minimum absolute value to 1 and then print the product of all elements in the matrix as the result.
Follow the below steps to solve the problem:
- Find the number of negative numbers(say count) and 0s(say zeros) in the given matrix by traversing the matrix mat[][].
- If the count is even and zeros is 1, then print the product of all numbers in the matrix except that 0.
- Otherwise, find the minimum absolute element in the matrix, change it to 1 and then print the product of all numbers in the matrix as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate maximum // product of a matrix by multiplying // pair of adjacent cells with -1 int maxProduct(vector<vector< int > > arr) { int N = arr.size(); // Stores the count of negative // numbers in the given matrix int cnt = 0; // Stores the count of 0s in // the given matrix arr[][] int zeros = 0; // Stores the minimum absolute value int maxValue = INT_MIN; vector< int > v; // Traverse the given matrix for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) { // Count negative numbers if (arr[i][j] < 0) { // Update the maximum // negative value maxValue = max(maxValue, arr[i][j]); cnt++; } // Increment the count // of 0s if exists if (arr[i][j] == 0) zeros++; } } // If there are more than one // 0, then print product as 0 if (zeros > 1) { cout << "0" ; } int product = 1; // Otherwise, find the product of all // the elements of the matrix arr[][] for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) { if (arr[i][j] == 0) continue ; // Update the product product *= (arr[i][j]); } } // If count of negative // elements is even if (cnt % 2 == 0) { return product; } return product / maxValue; } // Driver Code int main() { vector<vector< int > > mat = { { 2, -2 }, { -3, 1 } }; cout << maxProduct(mat); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to calculate maximum // product of a matrix by multiplying // pair of adjacent cells with -1 static int maxProduct( int [][] arr) { int N = arr.length; // Stores the count of negative // numbers in the given matrix int cnt = 0 ; // Stores the count of 0s in // the given matrix arr[][] int zeros = 0 ; // Stores the minimum absolute value int maxValue = Integer.MIN_VALUE; int v[]; // Traverse the given matrix for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < N; j++) { // Count negative numbers if (arr[i][j] < 0 ) { // Update the maximum // negative value maxValue = Math.max(maxValue, arr[i][j]); cnt++; } // Increment the count // of 0s if exists if (arr[i][j] == 0 ) zeros++; } } // If there are more than one // 0, then print product as 0 if (zeros > 1 ) { System.out.println( "0" ); } int product = 1 ; // Otherwise, find the product of all // the elements of the matrix arr[][] for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < N; j++) { if (arr[i][j] == 0 ) continue ; // Update the product product *= (arr[i][j]); } } // If count of negative // elements is even if (cnt % 2 == 0 ) { return product; } return product / maxValue; } // Driver Code public static void main(String[] args) { int [][] mat = { { 2 , - 2 }, { - 3 , 1 } }; System.out.println(maxProduct(mat)); } } // This code is contributed by sanjoy_62. |
Python3
# Python3 program for the above approach # Function to calculate maximum # product of a matrix by multiplying # pair of adjacent cells with -1 def maxProduct(arr): N = len (arr) # Stores the count of negative # numbers in the given matrix cnt = 0 # Stores the count of 0s in # the given matrix arr[][] zeros = 0 # Stores the minimum absolute value maxValue = - 10 * * 9 v = [] # Traverse the given matrix for i in range (N): for j in range (N): # Count negative numbers if (arr[i][j] < 0 ): # Update the maximum # negative value maxValue = max (maxValue, arr[i][j]) cnt + = 1 # Increment the count # of 0s if exists if (arr[i][j] = = 0 ): zeros + = 1 # If there are more than one # 0, then print product as 0 if (zeros > 1 ): print ( "0" ) product = 1 # Otherwise, find the product of all # the elements of the matrix arr[][] for i in range (N): for j in range (N): if (arr[i][j] = = 0 ): continue # Update the product product * = (arr[i][j]) # If count of negative # elements is even if (cnt % 2 = = 0 ): return product return product / / maxValue # Driver Code if __name__ = = '__main__' : mat = [ [ 2 , - 2 ], [ - 3 , 1 ] ] print (maxProduct(mat)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; class GFG{ // Function to calculate maximum // product of a matrix by multiplying // pair of adjacent cells with -1 static int maxProduct( int [,] arr) { int N = arr.GetLength(0); // Stores the count of negative // numbers in the given matrix int cnt = 0; // Stores the count of 0s in // the given matrix arr[][] int zeros = 0; // Stores the minimum absolute value int maxValue = Int32.MinValue; //int[] v; // Traverse the given matrix for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) { // Count negative numbers if (arr[i, j] < 0) { // Update the maximum // negative value maxValue = Math.Max(maxValue, arr[i, j]); cnt++; } // Increment the count // of 0s if exists if (arr[i, j] == 0) zeros++; } } // If there are more than one // 0, then print product as 0 if (zeros > 1) { Console.WriteLine( "0" ); } int product = 1; // Otherwise, find the product of all // the elements of the matrix arr[][] for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) { if (arr[i, j] == 0) continue ; // Update the product product *= (arr[i, j]); } } // If count of negative // elements is even if (cnt % 2 == 0) { return product; } return Math.Abs(product / maxValue); } // Driver code public static void Main(String []args) { int [,] mat = { { 2, -2 }, { -3, 1 } }; Console.Write(maxProduct(mat)); } } // This code is contriobuted by code_hunt |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to calculate maximum // product of a matrix by multiplying // pair of adjacent cells with -1 function maxProduct(arr) { let N = arr.length; // Stores the count of negative // numbers in the given matrix let cnt = 0; // Stores the count of 0s in // the given matrix arr[][] let zeros = 0; // Stores the minimum absolute value let maxValue = Number.MIN_VALUE; let v = new Array(); // Traverse the given matrix for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) { // Count negative numbers if (arr[i][j] < 0) { // Update the maximum // negative value maxValue = Math.max(maxValue, arr[i][j]); cnt++; } // Increment the count // of 0s if exists if (arr[i][j] == 0) zeros++; } } // If there are more than one // 0, then print product as 0 if (zeros > 1) { document.write( "0" ); } let product = 1; // Otherwise, find the product of all // the elements of the matrix arr[][] for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) { if (arr[i][j] == 0) continue ; // Update the product product *= (arr[i][j]); } } // If count of negative // elements is even if (cnt % 2 == 0) { return product; } return product / maxValue; } // Driver Code let mat = [[ 2, -2 ], [ -3, 1 ]]; document.write(maxProduct(mat)); </script> |
Output:
12
Time Complexity: O(N2)
Auxiliary Space: O(1)
Contact Us