Construct a Matrix with no element exceeding X and sum of two adjacent elements not exceeding Y
Given four integers N, M, X and Y, the task is to construct a N * M matrix such that each cell consists of a value in the range [0, X] such that sum of any two adjacent cells should be less than or equal to Y and the total sum of the matrix should be maximum.
Example:
Input: N = 3, M = 3, X = 5, Y = 3
Output:
3 0 3
0 3 0
3 0 3
Explanation:
All the values of the matrix are between 0 to 5.
The Sum of any two adjacent cells is equal to 3.
The total sum of the matrix is 15, which is maximum possible.Input: N = 3, M = 3, X = 3, Y = 5
Output:
3 2 3
2 3 2
3 2 3
Approach:
Follow the steps below to solve the problem:
- In order to satisfy the two necessary conditions, the matrix needs to be filled with only the following two numbers alternately:
First number = minimum(X, Y)
Second number = minimum(2X, Y) – First Number
Illustration:
N = 3, M = 3, X = 5, Y = 3
First Number = Minimum(X, Y) = Minimum(5, 3) = 3
Second Number = Minimum(2X, Y) – 3 = Minimum(10, 3) – 3 = 3 – 3 = 0
Therefore, sum of any two adjacent cells = 3 + 0 = 3(= Y)
- Finally, print the two numbers alternately, first number followed by the second number to maximize the sum of the matrix.
Below is the implementation of the above approach.
C++
// C++ implementation of // the above approach #include <iostream> using namespace std; // Function to print the // required matrix void FindMatrix( int n, int m, int x, int y) { int a, b, i, j; // For 1*1 matrix if (n * m == 1) { if (x > y) { cout << y << "\n" ; } else { cout << x << "\n" ; } return ; } // Greater number a = min(x, y); // Smaller number b = min(2 * x, y) - a; // Sets/Resets for alternate // filling of the matrix bool flag = true ; // Print the matrix for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { if (flag) cout << a << ' ' ; else cout << b << ' ' ; flag = !flag; } // If end of row is reached if (((n % 2 != 0 && m % 2 == 0) || (n % 2 == 0 && m % 2 == 0))) flag = !flag; cout << "\n" ; } } // Driver Code int main() { int N, M, X, Y; N = 3; M = 3; X = 5; Y = 3; FindMatrix(N, M, X, Y); } |
Java
// Java implementation of // the above approach import java.io.*; public class GFG{ // Function to print the // required matrix static void FindMatrix( int n, int m, int x, int y) { int a, b, i, j; // For 1*1 matrix if (n * m == 1 ) { if (x > y) { System.out.print(y + "\n" ); } else { System.out.print(x + "\n" ); } return ; } // Greater number a = Math.min(x, y); // Smaller number b = Math.min( 2 * x, y) - a; // Sets/Resets for alternate // filling of the matrix boolean flag = true ; // Print the matrix for (i = 0 ; i < n; i++) { for (j = 0 ; j < m; j++) { if (flag) System.out.print(a + " " ); else System.out.print(b + " " ); flag = !flag; } // If end of row is reached if (((n % 2 != 0 && m % 2 == 0 ) || (n % 2 == 0 && m % 2 == 0 ))) flag = !flag; System.out.print( "\n" ); } } // Driver Code public static void main(String[] args) { int N, M, X, Y; N = 3 ; M = 3 ; X = 5 ; Y = 3 ; FindMatrix(N, M, X, Y); } } // This code is contributed by gauravrajput1 |
Python3
# Python3 implementation of # the above approach # Function to print the # required matrix def FindMatrix(n, m, x, y): # For 1*1 matrix if (n * m = = 1 ): if (x > y): print (y) else : print (x) return # Greater number a = min (x, y) # Smaller number b = min ( 2 * x, y) - a # Sets/Resets for alternate # filling of the matrix flag = True # Print the matrix for i in range (n): for j in range (m): if (flag): print (a, end = " " ) else : print (b, end = " " ) flag = not flag # If end of row is reached if (((n % 2 ! = 0 and m % 2 = = 0 ) or (n % 2 = = 0 and m % 2 = = 0 ))): flag = not flag print () # Driver Code N = 3 M = 3 X = 5 Y = 3 FindMatrix(N, M, X, Y) # This code is contributed by chitranayal |
C#
// C# implementation of // the above approach using System; class GFG{ // Function to print the // required matrix static void FindMatrix( int n, int m, int x, int y) { int a, b, i, j; // For 1*1 matrix if (n * m == 1) { if (x > y) { Console.Write(y + "\n" ); } else { Console.Write(x + "\n" ); } return ; } // Greater number a = Math.Min(x, y); // Smaller number b = Math.Min(2 * x, y) - a; // Sets/Resets for alternate // filling of the matrix bool flag = true ; // Print the matrix for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { if (flag) Console.Write(a + " " ); else Console.Write(b + " " ); flag = !flag; } // If end of row is reached if (((n % 2 != 0 && m % 2 == 0) || (n % 2 == 0 && m % 2 == 0))) flag = !flag; Console.Write( "\n" ); } } // Driver Code public static void Main(String[] args) { int N, M, X, Y; N = 3; M = 3; X = 5; Y = 3; FindMatrix(N, M, X, Y); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript implementation of // the above approach // Function to print the // required matrix function FindMatrix(n, m, x, y) { var a, b, i, j; // For 1*1 matrix if (n * m == 1) { if (x > y) { document.write(y); } else { document.write(x); } return ; } // Greater number a = Math.min(x, y); // Smaller number b = Math.min(2 * x, y) - a; // Sets/Resets for alternate // filling of the matrix var flag = true ; // Print the matrix for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { if (flag) document.write(a + " " ); else document.write(b + " " ); flag = !flag; } // If end of row is reached if (((n % 2 != 0 && m % 2 == 0) || (n % 2 == 0 && m % 2 == 0))) flag = !flag; document.write( "<br>" ); } } // Driver Code var N, M, X, Y; N = 3; M = 3; X = 5; Y = 3; FindMatrix(N, M, X, Y); // This code is contributed by Khushboogoyal499 </script> |
3 0 3 0 3 0 3 0 3
Time complexity: O(N * M)
Space complexity: O(1)
Contact Us