Given two arrays row[] and col[] of size N and M respectively, the task is to construct a matrix of dimensions N × M such that the sum of matrix elements in every ith row is row[i] and the sum of matrix elements in every jth column is col[j].
Examples:
Input: row[] = {5, 7, 10}, col[] = {8, 6, 8}
Output: {{0, 5, 0}, {6, 1, 0}, {2, 0, 8}}
Explanation:
Row 1 has sum equal to 5 and column 1 has sum equal to 8
Row 2 has sum equal to 7 and column 2 has sum equal to 6
Row 3 has sum equal to 10 and column 3 has sum equal to 8Input: row[] ={1, 0}, col[] = {1}
Output: {{1}, {0}}
Explanation:
Row 1 has sum equal to 1 and column 1 has sum equal to 1
Row 2 has sum 0
Approach: The simplest approach to solve this problem is to use a Greedy Approach. Follow the steps below to solve this problem:
- Initialize a matrix having dimensions N × M.
- Start filling each cell (i, j) of the matrix in the following manner:
- For each cell (i, j), choose the minimum value of row[i], col[j], and place it at cell (i, j). Let it be minm.
- Subtract minm from row[i] and col[j].
- After completing the above steps, print the matrix formed.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to generate a matrix with// sum of each row equal to sum of r[]// and sum of each column equal to sum of c[]vector<vector<int> > restoreGem( vector<int>& r, vector<int>& c){ // Initialize a matrix vector<vector<int> > dp(r.size(), vector<int>(c.size(), 0)); // Traverse each cell (i, j) of the matrix for (int i = 0; i < r.size(); i++) { for (int j = 0; j < c.size(); j++) { // Assign the minimum of the // row or column value int m = min(r[i], c[j]); dp[i][j] = m; // Subtract the minimum from // both row and column sum r[i] -= m; c[j] -= m; } } return dp;}void printMatrix(vector<vector<int> > ans, int N, int M){ // Print the matrix obtained for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cout << ans[i][j] << " "; } cout << endl; }}// Driver Codeint main(){ vector<int> rowSum = { 5, 7, 10 }; vector<int> colSum = { 8, 6, 8 }; vector<vector<int> > ans = restoreGem(rowSum, colSum); printMatrix(ans, rowSum.size(), colSum.size());} |
Java
// Java program for the above approachimport java.io.*;class GFG{// Function to generate a matrix with// sum of each row equal to sum of r[]// and sum of each column equal to sum of c[]static int[][] restoreGem(int[] r, int[] c){ // Initialize a matrix int[][] dp = new int[r.length][c.length]; // Traverse each cell (i, j) of the matrix for (int i = 0; i < r.length; i++) { for (int j = 0; j < c.length; j++) { // Assign the minimum of the // row or column value int m = Math.min(r[i], c[j]); dp[i][j] = m; // Subtract the minimum from // both row and column sum r[i] -= m; c[j] -= m; } } return dp;}static void printMatrix(int[][] ans, int N, int M){ // Print the matrix obtained for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { System.out.print(ans[i][j] + " "); } System.out.println(); }}// Driver Codepublic static void main(String[] args){ int[] rowSum = { 5, 7, 10 }; int[] colSum = { 8, 6, 8 }; int[][] ans = restoreGem(rowSum, colSum); printMatrix(ans, rowSum.length, colSum.length);}}// This code is contributed by susmitakundugoaldanga. |
Python3
# Python program for the above approach# Function to generate a matrix with# sum of each row equal to sum of r[]# and sum of each column equal to sum of c[]def restoreGem(r, c): # Initialize a matrix dp = [] # Traverse each cell (i, j) of the matrix for i in range(0, len(r)): dp.append([]) for j in range(0, len(c)): # Assign the minimum of the # row or column value m = min(r[i], c[j]) dp[i].append(m) # Subtract the minimum from # both row and column sum r[i] -= m c[j] -= m return dpdef printMatrix(ans, N, M): # Print the matrix obtained for i in range(0, len(ans)): for j in range(0, len(ans[i])): print(ans[i][j], end=" ") print("\n")# Driver CoderowSum = [5, 7, 10]colSum = [8, 6, 8]ans = restoreGem(rowSum, colSum)printMatrix(ans, len(rowSum), len(colSum))# This code is contributed by rj13to. |
C#
// C# program for the above approachusing System;public class GFG{// Function to generate a matrix with// sum of each row equal to sum of r[]// and sum of each column equal to sum of c[]static int[,] restoreGem(int[] r, int[] c){ // Initialize a matrix int[,] dp = new int[r.Length, c.Length]; // Traverse each cell (i, j) of the matrix for (int i = 0; i < r.Length; i++) { for (int j = 0; j < c.Length; j++) { // Assign the minimum of the // row or column value int m = Math.Min(r[i], c[j]); dp[i,j] = m; // Subtract the minimum from // both row and column sum r[i] -= m; c[j] -= m; } } return dp;}static void printMatrix(int[,] ans, int N, int M){ // Print the matrix obtained for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { Console.Write(ans[i, j] + " "); } Console.WriteLine(); }}// Driver Codepublic static void Main(String[] args){ int[] rowSum = { 5, 7, 10 }; int[] colSum = { 8, 6, 8 }; int[,] ans = restoreGem(rowSum, colSum); printMatrix(ans, rowSum.Length, colSum.Length);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program of the above approach// Function to generate a matrix with// sum of each row equal to sum of r[]// and sum of each column equal to sum of c[]function restoreGem(r, c){ // Initialize a matrix let dp = new Array(r.length); // Loop to create 2D array using 1D array for (var i = 0; i < dp.length; i++) { dp[i] = new Array(2); } // Traverse each cell (i, j) of the matrix for (let i = 0; i < r.length; i++) { for (let j = 0; j < c.length; j++) { // Assign the minimum of the // row or column value let m = Math.min(r[i], c[j]); dp[i][j] = m; // Subtract the minimum from // both row and column sum r[i] -= m; c[j] -= m; } } return dp;}function printMatrix(ans, N, M){ // Print the matrix obtained for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { document.write(ans[i][j] + " "); } document.write("<br/>"); }} // Driver Code let rowSum = [ 5, 7, 10 ]; let colSum = [ 8, 6, 8 ]; let ans = restoreGem(rowSum, colSum); printMatrix(ans, rowSum.length, colSum.length);</script> |
Output:
5 0 0 3 4 0 0 2 8
Time Complexity: O(N×M)
Auxiliary Space: O(N×M)
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!
