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
Output
63
Time Complexity: O(R * C)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
