Given two matrices M1[][] and M2[][] of size R * C along with an integer X. In one operation select any cell of M1 let’s say M1[ i ][ j ] and update it as M1[ i ][ j ] +1 or M1[ i ][ j ] – 1, Then the task is to maximize the cell-wise product of elements by using the given operation X times. (Formally, ∑M1[ i ][ j ] * M2[ i ][ j ] for (1 ≤ i ≤ R), (1 ≤ j ≤ C) must be the maximum possible.)
Examples:
Input: R = 1, C = 2, X = 2, M1[][] = {1, 2}, M2[][] = {-2, 3}
Output: 10
Explanation:
- First operation: Update M1[1][2] as M1[1][2] + 1, then M1[][] = {1, 3}
- Second operation: Update M1[1][2] as M1[1][2] + 1, then M1[][] = {1, 4}
Now cell-wise product sum = M1[1][1] * M2[1][1] + M1[1][2] * M2[1][2] = (1 * -2) + (4 * 3) = -2 + 12 = 10 . It can be verified that no value of the sum of the product greater than 10 is possible using the given operations on M1[][].
Input: R = 3, C = 2, X = 4, M1[][] = {{1, 2}, {4, 5}, {3, -1}}, M2[][] = {{-2, 3}, {5, 6}, {-8, -1}}
Output: 63
Explanation: It can be verified that the maximum possible sum will be 63. Therefore, the output is 63.
Approach: Implement the idea below to solve the problem
The problem is observation based and it can be observed that the maximum possible sum of cell-wise product can be achieved by adding or subtracting 1, X times to an element of M1[][] optimally. There will be an element guaranteed, which will provide the max value of the sum using the given operation X times.
Steps were taken to solve the problem:
- Calculate the cell-wise sum of the product of elements in a variable let’s say Sum by traversing both matrices.
- Then increment and decrement each element of M1[][] X times, If a current sum greater than Sum is found then update Sum.
- Print the value of the sum.
Below is the implementation for the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Method for obtaining maximum possible sum void maximumSum(vector<vector<int>>& M1, vector<vector<int>>& M2, int X) { // variable for holding cell-wise // sum of both matrix long long sum = 0; // Loop for calculating cell-wise // sum of product of elements for (int i = 0; i < M1.size(); i++) { for (int j = 0; j < M1[0].size(); j++) { sum += (M1[i][j] * M2[i][j]); } } // Temporary variable for holding // initial value of sum long long temp = sum; // Loops for traversing on M1[][] // and applying operations for (int i = 0; i < M1.size(); i++) { for (int j = 0; j < M1[0].size(); j++) { // Two variables which will // store sum to see effect // of Decrementing and // Incrementing an element // of M1[][] X times long long Z = temp; long long Y = temp; // Z is holding the sum // when an element of M1[][] // is Decremented X times Z = Z - (M1[i][j] * M2[i][j]); Z = Z + ((M1[i][j] - X) * M2[i][j]); // Y is holding the sum // when an element of M1[][] // is Incremented X times Y = Y - (M1[i][j] * M2[i][j]); Y = Y + ((M1[i][j] + X) * M2[i][j]); // Updating Sum if maximum sum // is found on incrementing or // decrementing operations sum = max(sum, max(Z, Y)); } } // Printing Maximum possible sum cout << sum << "\n"; } // Calling the main function int main() { int R = 3, C = 2, X = 4; vector<vector<int>> M1 = { { 1, 2 }, { 4, 5 }, { 3, -1 } }; vector<vector<int>> M2 = { { -2, 3 }, { 5, 6 }, { -8, -1 } }; // Function call maximumSum(M1, M2, X); return 0; } // This code is contributed by Ritesh Jha
Java
// JAVA program to implement the approach class GFG { // Driver function public static void main(String[] args) { // Inputs int R = 3, C = 2, X = 4; int M1[][] = { { 1, 2 }, { 4, 5 }, { 3, -1 } }; int M2[][] = { { -2, 3 }, { 5, 6 }, { -8, -1 } }; // Function call maximumSum(M1, M2, X); } // Method for obtaining maximum // possible sum static void maximumSum(int[][] M1, int M2[][], int X) { // variable for holding cell-wise // sum of both matrix long sum = 0; // Loop for calculating cell-wise // sum of product of elements for (int i = 0; i < M1.length; i++) for (int j = 0; j < M1[0].length; j++) sum += (M1[i][j] * M2[i][j]); // Temporary variable for holding // initial value of sum long temp = sum; // Loops for traversing on M1[][] // and applying operations for (int i = 0; i < M1.length; i++) { for (int j = 0; j < M1[0].length; j++) { // Two variables which will // store sum to see effect // of Decrementing and // Incrementing an element // of M1[][] X times long Z = temp; long Y = temp; // Z is holding the sum // when an element of M1[][] // is Decremented X times Z = Z - (M1[i][j] * M2[i][j]); Z = Z + ((M1[i][j] - X) * M2[i][j]); // Y is holding the sum // when an element of M1[][] // is Incremented X times Y = Y - (M1[i][j] * M2[i][j]); Y = Y + ((M1[i][j] + X) * M2[i][j]); // Updating Sum if maximum sum // is found on incrmenting or // decrementing operations sum = Math.max(sum, Math.max(Z, Y)); } } // Printing Maximum possible sum System.out.println(sum); } }
Python3
# Method for obtaining maximum possible sum def maximumSum(M1, M2, X): # variable for holding cell-wise # sum of both matrix sum = 0 # Loop for calculating cell-wise # sum of product of elements for i in range(len(M1)): for j in range(len(M1[0])): sum += (M1[i][j] * M2[i][j]) # Temporary variable for holding # initial value of sum temp = sum # Loops for traversing on M1[][] # and applying operations for i in range(len(M1)): for j in range(len(M1[0])): # Two variables which will # store sum to see effect # of Decrementing and # Incrementing an element # of M1[][] X times Z = temp Y = temp # Z is holding the sum # when an element of M1[][] # is Decremented X times Z = Z - (M1[i][j] * M2[i][j]) Z = Z + ((M1[i][j] - X) * M2[i][j]) # Y is holding the sum # when an element of M1[][] # is Incremented X times Y = Y - (M1[i][j] * M2[i][j]) Y = Y + ((M1[i][j] + X) * M2[i][j]) # Updating Sum if maximum sum # is found on incrementing or # decrementing operations sum = max(sum, max(Z, Y)) # Printing Maximum possible sum print(sum) # Calling the main function R, C, X = 3, 2, 4 M1 = [[1, 2], [4, 5], [3, -1]] M2 = [[-2, 3], [5, 6], [-8, -1]] # Function call maximumSum(M1, M2, X) # This code is contributed by prasad264
C#
// C# program to implement the approach using System; using System.Collections.Generic; public class GFG { // Method for obtaining maximum possible sum public static void MaximumSum(List<List<int> > M1, List<List<int> > M2, int X) { // variable for holding cell-wise // sum of both matrix long sum = 0; // Loop for calculting cell-wise // sum of product of elements for (int i = 0; i < M1.Count; i++) { for (int j = 0; j < M1[0].Count; j++) { sum += (M1[i][j] * M2[i][j]); } } // Temporary variable for holding // initial value of sum long temp = sum; // Loops for traversing on M1[][] // and applying operations for (int i = 0; i < M1.Count; i++) { for (int j = 0; j < M1[0].Count; j++) { // Two variables which will // store sum to see effect // of Decrementing and // Incrementing an element // of M1[][] X times long Z = temp; long Y = temp; // Z is holding the sum // when an element of M1[][] // is Decremented X times Z = Z - (M1[i][j] * M2[i][j]); Z = Z + ((M1[i][j] - X) * M2[i][j]); // Y is holding the sum // when an element of M1[][] // is Incremented X times Y = Y - (M1[i][j] * M2[i][j]); Y = Y + ((M1[i][j] + X) * M2[i][j]); // Updating Sum if maximum sum // is found on incrmenting or // decrementing operations sum = Math.Max(sum, Math.Max(Z, Y)); } } // Printing Maximum possible sum Console.WriteLine(sum); } // Calling the main function public static void Main() { int R = 3, C = 2, X = 4; List<List<int> > M1 = new List<List<int> >{ new List<int>{ 1, 2 }, new List<int>{ 4, 5 }, new List<int>{ 3, -1 } }; List<List<int> > M2 = new List<List<int> >{ new List<int>{ -2, 3 }, new List<int>{ 5, 6 }, new List<int>{ -8, -1 } }; // Function call MaximumSum(M1, M2, X); } } // This code is contributed by prasad264
Javascript
// Method for obtaining maximum possible sum function maximumSum(M1, M2, X) { // variable for holding cell-wise // sum of both matrix let sum = 0; // Loop for calculating cell-wise // sum of product of elements for (let i = 0; i < M1.length; i++) { for (let j = 0; j < M1[0].length; j++) { sum += (M1[i][j] * M2[i][j]); } } // Temporary variable for holding // initial value of sum let temp = sum; // Loops for traversing on M1[][] // and applying operations for (let i = 0; i < M1.length; i++) { for (let j = 0; j < M1[0].length; j++) { // Two variables which will // store sum to see effect // of Decrementing and // Incrementing an element // of M1[][] X times let Z = temp; let Y = temp; // Z is holding the sum // when an element of M1[][] // is Decremented X times Z = Z - (M1[i][j] * M2[i][j]); Z = Z + ((M1[i][j] - X) * M2[i][j]); // Y is holding the sum // when an element of M1[][] // is Incremented X times Y = Y - (M1[i][j] * M2[i][j]); Y = Y + ((M1[i][j] + X) * M2[i][j]); // Updating Sum if maximum sum // is found on incrementing or // decrementing operations sum = Math.max(sum, Math.max(Z, Y)); } } // Printing Maximum possible sum console.log(sum); } // Calling the main function const R = 3, C = 2, X = 4; const M1 = [ [1, 2], [4, 5], [3, -1] ]; const M2 = [ [-2, 3], [5, 6], [-8, -1] ]; // Function call maximumSum(M1, M2, X); // Contributed by adityasha4x71
63
Time Complexity: O(R * C)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!