Multiply a Square Matrix by Itself

medium Matrix (2D arrays)

Problem

A square matrix A is given. Print A times A (the matrix product). The cell (i, j) of the result is the sum over k of A[i][k] * A[k][j]. Input: n and n, then the matrix. Print n rows.

Constraints

  • 1 <= n <= 20
  • |a[i][j]| <= 100

Examples

Input

2 2
1 2
3 4

Output

7 10
15 22

Solutions

Best approachTime O(n^3)Space O(n^2)

Each result cell needs n multiplications, and there are n * n cells, so O(n^3). The loop order i, j, k follows the definition directly.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Matrix square.
 * Input   : n, n, then the matrix.
 * Output  : n rows.
 * Approach: Dot products.
 * Time    : O(n^3)
 * Space   : O(n^2)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(int[][] m) {
        // Step 1: Result cell (i, j) is the dot product of row i of A and column j of A.
        int n = m.length;
        String[] lines = new String[n];
        for (int i = 0; i < n; i++) {
            StringBuilder row = new StringBuilder();
            for (int j = 0; j < n; j++) {
                long sum = 0;
                for (int k = 0; k < n; k++) {
                    sum += (long) m[i][k] * m[k][j];
                }
                row.append(j == 0 ? "" : " ").append(sum);
            }
            lines[i] = row.toString();
        }
        return lines;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int rows = scanner.nextInt();
        int cols = scanner.nextInt();
        int[][] m = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                m[i][j] = scanner.nextInt();
            }
        }
        System.out.println(String.join("\n", solve(m)));
    }
}
Hints (2)
  1. How many cells does the result have?
  2. Which row and column make cell (1, 0)?