const int mod = 1e9+7;
void multiply(long long int F[2][2], long long int M[2][2]);
void power(long long int F[2][2], long long int n);

int fib(long long int n)
{
long long int F[2][2] = {{1, 1}, {1, 0}};
if (n == 0) return 0;
power(F, n - 1);
return F[0][0];
}
void power(long long int F[2][2], long long int n)
{
if(n == 0 || n == 1) return;

long long int M[2][2] = {{1, 1}, {1, 0}};

power(F, n / 2);
multiply(F, F);

if (n % 2 != 0)
multiply(F, M);
}
void multiply(long long int F[2][2], long long int M[2][2])
{
int x = ((F[0][0]%mod * M[0][0]%mod)%mod + (F[0][1]%mod * M[1][0]%mod)%mod)%mod;
int y = ((F[0][0]%mod * M[0][1]%mod)%mod + (F[0][1]%mod * M[1][1]%mod)%mod)%mod;
int z = ((F[1][0]%mod * M[0][0]%mod)%mod + (F[1][1]%mod * M[1][0]%mod)%mod)%mod;
int w = ((F[1][0]%mod * M[0][1]%mod)%mod + (F[1][1]%mod * M[1][1]%mod)%mod)%mod;

F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
// call using fib(n)
#include<iostream>
using namespace std;

class MATRIX{
int row;
int col;
int **array;
public:
MATRIX();
MATRIX(const MATRIX&);
MATRIX(int,int);
void takeinput();
MATRIX operator+(MATRIX);
MATRIX operator-(MATRIX);
bool operator==(MATRIX);
friend ostream& operator<<(ostream&,MATRIX);
~MATRIX();
};
int main(){

int r,c;
cout<<"Enter number of rows for matrix m1: ";
cin>>r;
cout<<"Enter number of columns for matrix m1: ";
cin>>c;
MATRIX m1(r,c);
m1.takeinput();
cout<<"Enter number of rows for matrix m2: ";
cin>>r;
cout<<"Enter number of columns for matrix m2: ";
cin>>c;
MATRIX m2(r,c);
m2.takeinput();
cout<<"Matrix m1 :-"<<endl<<m1;
cout<<"Matrix m2 :-"<<endl<<m2;
MATRIX m3,m4;
if(m1==m2){
MATRIX m3 = m1 + m2;
cout<<"Matrix m3 :-"<<endl;
cout<<m3;
MATRIX m4 = m1 - m2;
cout<<"Matrix m4 :-"<<endl;
cout<<m4;
}
else{
cout<<"Error! The dimensions of both the operand matrices are not same\n";
}
return 0;
}

MATRIX::MATRIX(int r,int c){
row = r;
col = c;
array = new int*[r];
for(int i=0;i<r;i++){
array[i] = new int[c];
for(int j=0;j<c;j++) {
array[i][j] = 0;
}
}
}
MATRIX::MATRIX(const MATRIX& obj){
row = obj.row;
col = obj.col;
array = new int*[row];
for(int i=0;i<row;i++){
array[i] = new int[col];
for(int j=0;j<col;j++){
array[i][j] = obj.array[i][j];
}
}
}
void MATRIX::takeinput(){
for(int i=1;i<=row;i++){
for(int j=1;j<=col;j++){
cout<<"Enter ("<<i<<", "<<j<<") element: ";
cin>>array[i-1][j-1];
}
}
}
MATRIX::MATRIX(){
row=0;
col=0;
array=NULL;
}
MATRIX MATRIX::operator+(MATRIX m2){
MATRIX output(row,col);
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
output.array[i][j] = array[i][j] + m2.array[i][j];
}
}
return output;
}
MATRIX MATRIX::operator-(MATRIX m2){
MATRIX output(row,col);
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
output.array[i][j] = array[i][j] - m2.array[i][j];
}
}
return output;
}
ostream& operator<<(ostream &print, MATRIX m){
for(int i=0;i<m.row;i++){
for(int j=0;j<m.col;j++){
print<<m.array[i][j]<<" ";
}
print<<endl;
}
return print;
}
bool MATRIX::operator==(MATRIX m2){
return (row==m2.row && col==m2.col) ? true:false;
}

MATRIX::~MATRIX(){
for(int i=0;i<row;i++){
delete []array[i];
}
delete []array;
}
def spiral(matrix, r, c):
circular = []

start_row, end_row = 0, r
start_col, end_col = 0, c

while start_row < end_row and start_col < end_col:

for i in range(start_col, end_col):
circular.append(matrix[start_row][i])
start_row += 1

for i in range(start_row, end_row):
circular.append(matrix[i][end_col-1])
end_col -= 1

for i in range(end_col, start_col, -1):
circular.append(matrix[end_row-1][i-1])
end_row -= 1

for i in range(end_row, start_row, -1):
circular.append(matrix[i-1][start_col])
start_col += 1

return circular
class Solution
{
//Function to find minimum number of operations that are required
//to make the matrix beautiful.
static int findMinOperation(int matrix[][], int n)
{
int sumRow[] = new int[n];
int sumCol[] = new int[n];
Arrays.fill(sumRow, 0);
Arrays.fill(sumCol, 0);

//calculating sumRow[] and sumCol[] array.
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
sumRow[i] += matrix[i][j];
sumCol[j] += matrix[i][j];

}
}

//finding maximum sum value in either row or in column.
int maxSum = 0;
for (int i = 0; i < n; ++i)
{
maxSum = Math.max(maxSum, sumRow[i]);
maxSum = Math.max(maxSum, sumCol[i]);
}

int count = 0;
for (int i = 0, j = 0; i < n && j < n;)
{
//finding minimum increment required in either row or column.
int diff = Math.min(maxSum - sumRow[i], maxSum - sumCol[j]);

//sumRow[] and sumCol[] array.
matrix[i][j] += diff;
sumRow[i] += diff;
sumCol[j] += diff;

//updating the result.
count += diff;

//if ith row is satisfied, incrementing i for next iteration.
if (sumRow[i] == maxSum)
++i;

//if jth column is satisfied, incrementing j for next iteration.
if (sumCol[j] == maxSum)
++j;
}
//returning the result.
return count;
}
}
class Solution
{
//Function to modify the matrix such that if a matrix cell matrix[i][j]
//is 1 then all the cells in its ith row and jth column will become 1.
void booleanMatrix(int matrix[][])
{
int r = matrix.length;
int c = matrix[0].length;

//using two list to keep track of the rows and columns
//that needs to be updated with 1.
int row[] = new int[r];
int col[] = new int[c];

for(int i = 0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
//if we get 1 in matrix, we mark ith row and jth column as 1.
if(matrix[i][j] == 1){
row[i] = 1;
col[j] = 1;
}
}
}

for(int i =0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
//if ith row or jth column is marked as 1, then all elements
//of matrix in that row and column will be 1.
if(row[i] == 1 || col[j] == 1){
matrix[i][j] = 1;
}
}
}
}
}
class Solution
{
//Function to interchange the rows of a matrix.
static void interchangeRows(int matrix[][])
{
for(int i=0;i<matrix.length/2;i++){
for(int j=0;j<matrix[i].length;j++){
int temp=matrix[i][j];
matrix[i][j]=matrix[matrix.length-i-1][j];
matrix[matrix.length-i-1][j]=temp;
}
}
}
}
class Solution
{
//Function to reverse the columns of a matrix.
static void reverseCol(int matrix[][])
{
for(int i=0; i<matrix.length; i++){
for(int j=0; j<matrix[i].length/2; j++)
{
int temp = matrix[i][j];
matrix[i][j] = matrix[i][matrix[i].length-j-1];
matrix[i][matrix[i].length-j-1] = temp;
}
}
}
}
class Solution
{
//Function to exchange first column of a matrix with its last column.
static void exchangeColumns(int matrix[][])
{
int temp = 0;
for (int i=0; i<matrix.length; i++)
{
temp = matrix[i][0];
matrix[i][0] = matrix[i][matrix[i].length-1];
matrix[i][matrix[i].length-1] = temp;
}
}
}
class Solution
{
//Function to get cofactor of matrix[p][q] in temp[][].
static void getCofactor(int matrix[][], int temp[][], int p, int q, int n)
{
int i = 0, j = 0;

for (int row = 0; row < n; row++)
{
for (int col = 0; col < n; col++)
{
//copying only those elements into temporary matrix
//which are not in given row and column.
if(row != p && col != q)
{
temp[i][j++] = matrix[row][col];

//if row is filled, we increase row index and
//reset column index.
if(j == n - 1)
{
j = 0;
i++;
}
}
}
}
}

//Function for finding determinant of matrix.
static int determinantOfMatrix(int matrix[][], int n)
{
int D = 0;

//base case
if (n == 1)
return matrix[0][0];

//creating a list to store Cofactors.
int temp[][]  = new int[n][n];

int sign = 1;

//iterating for each element of first row.
for (int i = 0; i < n; i++)
{
//getting Cofactor of matrix[0][i].
getCofactor(matrix, temp, 0, i, n);
D += sign * matrix[0][i] * determinantOfMatrix(temp, n - 1);

//terms are to be added with alternate sign so changing the sign.
sign = -sign;
}
//returning the determinant.
return D;
}
}
class Solution
{
//Function to multiply two matrices.
static int[][] multiplyMatrix(int A[][], int B[][])
{
int n1 = a.length;
int m1 = a[0].length;
int n2 = b.length;
int m2 = b[0].length;

if(m1!=n2)
{
int arr0[][] = new int[1][1];
arr0[0][0] = -1;
return arr0;
}

int arr[][] = new int[n1][m2];

for(int i = 0 ; i<n1 ; i++)
for(int j = 0 ; j<m2 ; j++)
for(int q = 0; q<n2 ; q++)
arr[i][j]+= a[i][q]*b[q][j];

return arr;
}
}
class Solution
{
//Function to return sum of upper and lower triangles of a matrix.
static ArrayList<Integer> sumTriangles(int matrix[][], int n)
{
ArrayList<Integer> list=new ArrayList<>();
int sum1=0;
int sum2=0;
for(int g=0; g<matrix.length; g++){
for(int i=0, j=g; j<matrix.length; i++,j++){
sum1+=matrix[i][j];
}
}
for(int g=0; g<matrix.length; g++){
for(int i=g,j=0; i<matrix.length; i++,j++){
sum2+=matrix[i][j];
}
}
return list;
}
}
class Solution
{
static int[][] sumMatrix(int A[][], int B[][])
{
int n = A.length, m = A[0].length;
int res[][] = new int[0][0];
//Check if two input matrix are of different dimensions
if(n != B.length || m != B[0].length)
return res;

res = new int[n][m];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
res[i][j] = A[i][j] + B[i][j];

return res;
}
}
// Time Complexity : O(r * log(max - min) * logC)

import java.util.Arrays;

public class MedianInRowSorted
{
static public int matMed(int mat[][], int r ,int c)
{
int min = mat[0][0], max = mat[0][c-1];
for (int i=1; i<r; i++)
{
if (mat[i][0] < min)
min = mat[i][0];

if (mat[i][c-1] > max)
max = mat[i][c-1];
}

int medPos = (r * c + 1) / 2;
while (min < max)
{
int mid = (min + max) / 2;
int midPos = 0;
int pos = 0;
for (int i = 0; i < r; ++i){
pos = Arrays.binarySearch(mat[i],mid);

if(pos < 0)
pos = Math.abs(pos) - 1;

else
{
while(pos < mat[i].length && mat[i][pos] == mid)
pos += 1;
}

midPos = midPos + pos;
}
if (midPos < medPos)
min = mid + 1;
else
max = mid;
}
return min;
}

public static void main(String[] args)
{
int r = 3, c = 5;
int m[][]= { {5,10,20,30,40}, {1,2,3,4,6}, {11,13,15,17,19} };
System.out.println("Median is " + matMed(m, r, c));

}
}
// Efficient Code : Time Complexity : O(R + C)

import java.util.*;
import java.io.*;

class GFG
{
static int R = 4, C = 4;

static void search(int mat[][], int x)
{
int i  = 0, j = C - 1;

while(i < R && j >= 0)
{
if(mat[i][j] == x)
{
System.out.println("Found at (" + i + ", " + j + ")");
return;
}
else if(mat[i][j] > x)
{
j--;
}
else
{
i++;
}
}
}

public static void main(String args[])
{
int arr[][] = {{10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 35, 45},
{32, 33, 39, 50}};
int x = 29;

search(arr, x);

}
}

// Naive Code : Time Complexity : O(R * C)

static int R = 4, C = 4;

static void search(int mat[][], int x)
{
for(int i = 0; i < R; i++)
{
for(int j = 0; j < C; j++)
{
if(mat[i][j] == x)
{
System.out.println("Found at (" + i + ", " + j + ")");

return;
}
}
}

}
import java.util.*;
import java.io.*;

class GFG
{
static void printSpiral(int mat[][], int R, int C)
{
int top = 0, left = 0, bottom = R - 1, right = C - 1;

while(top <= bottom && left <= right)
{
for(int i = left; i <= right; i++)
System.out.print(mat[top][i] + " ");

top++;

for(int i = top; i <= bottom; i++)
System.out.print(mat[i][right] + " ");

right--;

if(top <= bottom){
for(int i = right; i >= left; i--)
System.out.print(mat[bottom][i] + " ");

bottom--;
}

if(left <= right){
for(int i = bottom; i >= top; i--)
System.out.print(mat[i][left] + " ");

left++;
}
}
}

public static void main(String args[])
{
int arr[][] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};

printSpiral(arr, 4, 4);
}
}
// Efficient Code : Time Complexity : O(n^2), Auxiliary Space : O(1)

import java.util.*;
import java.io.*;

class GFG
{
static int n = 4;

static void swap(int mat[][], int i, int j)
{
int temp = mat[i][j];
mat[i][j] = mat[j][i];
mat[j][i] = temp;
}

static void swap2(int low, int high, int i, int mat[][])
{
int temp = mat[low][i];
mat[low][i] = mat[high][i];
mat[high][i] = temp;
}

static void rotate90(int mat[][])
{
// Transpose
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
swap(mat, i, j);

// Reverse columns
for(int i = 0; i < n; i++)
{
int low = 0, high = n - 1;

while(low < high)
{
swap2(low, high, i, mat);

low++;
high--;
}
}
}

public static void main(String args[])
{
int arr[][] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};

rotate90(arr);

for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
System.out.print(arr[i][j]+" ");
}

System.out.println();
}
}
}

// Naive Code : Time Complexity : O(n^2), Space Complexity : O(n^2)

static int n = 4;

static void rotate90(int mat[][])
{
int temp[][] = new int[n][n];

for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
temp[n - j - 1][i] = mat[i][j];

for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
mat[i][j] = temp[i][j];

}

// last column becomes first row
// second last column becomes second row
// Efficient Code : Without Using Auxiliary Array

import java.util.*;
import java.io.*;

class GFG
{
static int n = 4;

static void swap(int mat[][], int i, int j)
{
int temp = mat[i][j];
mat[i][j] = mat[j][i];
mat[j][i] = temp;
}

static void transpose(int mat[][])
{

for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
swap(mat, i, j);
}

public static void main(String args[])
{
int arr[][] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};

transpose(arr);

for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
System.out.print(arr[i][j]+" ");
}

System.out.println();
}
}
}

// Naive Code :

static int n = 4;

static void transpose(int mat[][])
{
int temp[][] = new int[n][n];

for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
// copy
temp[i][j] = mat[j][i]; // temp[i][j] = mat[i][j];

for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
// copy back to original array
mat[i][j] = temp[i][j];

}
import java.util.*;
import java.io.*;

class GFG
{
static int R = 4, C = 4;

static void bTraversal(int mat[][])
{
if(R == 1)
{
for(int i = 0; i < C; i++)
System.out.print(mat[0][i] + " ");
}
else if(C == 1)
{
for(int i = 0; i < R; i++)
System.out.print(mat[i][0] + " ");
}
else
{
for(int i = 0; i < C; i++)
System.out.print(mat[0][i] + " ");
for(int i = 1; i < R; i++)
System.out.print(mat[i][C - 1] + " ");
for(int i = C - 2; i >= 0; i--)
System.out.print(mat[R - 1][i] + " ");
for(int i = R - 2; i >= 1; i--)
System.out.print(mat[i][0] + " ");
}
}

public static void main(String args[])
{
int arr[][] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};

bTraversal(arr);
}
}
import java.util.*;
import java.io.*;

class GFG
{
static int R = 4, C = 4;
static void printSnake(int mat[][])
{
for(int i = 0; i < R; i++)
{
if(i % 2 == 0)
{
for(int j = 0; j < C; j++)
System.out.print(mat[i][j] + " ");
}
else
{
for(int j = C - 1; j >= 0; j--)
System.out.print(mat[i][j] + " ");
}
}
}

public static void main(String args[])
{
int arr[][] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};

printSnake(arr);
}
}
star

Tue May 09 2023 16:32:06 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/37f36b318a7d99c81f17f0a54fc46b5ce06bbe8c/1

#fibonacci #matrix
star

Sat May 07 2022 05:20:37 GMT+0000 (Coordinated Universal Time)

#c++ #matrix
star

Sun Feb 20 2022 23:00:36 GMT+0000 (Coordinated Universal Time)

#python #matrix #spiral
star

Tue Feb 08 2022 09:38:53 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/make-matrix-beautiful-1587115620/1/?track=DSASP-Matrix&batchId=190

#java #gfg #geeksforgeeks #2d #array #matrix #practice #beautifulmatrix
star

Tue Feb 08 2022 09:35:30 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/boolean-matrix-problem-1587115620/1/?track=DSASP-Matrix&batchId=190

#java #gfg #geeksforgeeks #2d #array #matrix #practice #booleanmatrix
star

Tue Feb 08 2022 09:32:41 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/reversing-the-rows-of-a-matrix-1587115621/1/?track=DSASP-Matrix&batchId=190

#java #gfg #geeksforgeeks #2d #array #matrix #practice #interchangingrows
star

Tue Feb 08 2022 08:47:50 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/reversing-the-columns-of-a-matrix-1587115621/1/?track=DSASP-Matrix&batchId=190

#java #gfg #geeksforgeeks #2d #array #matrix #practice #reversingcolumns
star

Tue Feb 08 2022 08:41:01 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/exchange-matrix-columns-1587115620/1/?track=DSASP-Matrix&batchId=190

#java #gfg #geeksforgeeks #2d #array #matrix #practice #exchangecolumns
star

Tue Feb 08 2022 08:29:37 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/determinant-of-a-matrix-1587115620/1/?track=DSASP-Matrix&batchId=190

#java #gfg #geeksforgeeks #2d #array #matrix #practice #determinant
star

Tue Feb 08 2022 08:21:15 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/multiply-the-matrices-1587115620/1/?track=DSASP-Matrix&batchId=190

#java #gfg #geeksforgeeks #2d #array #matrix #practice #multiplication
star

Tue Feb 08 2022 08:14:36 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/sum-of-upper-and-lower-triangles-1587115621/1/?track=DSASP-Matrix&batchId=190

#java #gfg #geeksforgeeks #2d #array #matrix #practice #sum
star

Tue Feb 08 2022 08:09:29 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/adding-two-matrices3512/1/?track=DSASP-Matrix&batchId=190

#java #gfg #geeksforgeeks #2d #array #matrix #addition #practice
star

Tue Feb 08 2022 08:02:14 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #2d #array #matrix #median #rowwisesorted
star

Tue Feb 08 2022 07:54:06 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #2d #array #matrix #search
star

Tue Feb 08 2022 07:45:27 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #2d #array #matrix #spiraltraversal
star

Tue Feb 08 2022 07:40:52 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #2d #array #matrix #rotate90
star

Tue Feb 08 2022 07:29:55 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #2d #array #matrix #transpose
star

Tue Feb 08 2022 07:19:12 GMT+0000 (Coordinated Universal Time)

#java #gfg #geeksforgeeks #lecture #2d #array #matrix #snakepattern