Problem Statement

NOTE: This problem statement contains subscripts and superscripts which may not display properly for plugin users.

The elements of a two-dimensional matrix with M rows and N columns are usually stored as a linear array of length M*N. Assuming "row-major" order, elements are stored left-to-right, then top-to-bottom (the same order that we read English text on a written page). For example, the following matrix A, with M=3 and N=3:

    0 1 2
    3 4 5
    6 7 8

is stored as: { 0, 1, 2, 3, 4, 5, 6, 7, 8 }.

The transpose of a matrix A (denoted A^T) is obtained by exchanging its rows and columns. Element A^T_ij equals A_ji , and if A has M rows and N columns, A^T will have N rows and M columns. For example, the transpose of the above matrix is:

    0 3 6
    1 4 7
    2 5 8

and is stored as: { 0, 3, 6, 1, 4, 7, 2, 5, 8 }.

Computing the transpose of the square matrix "in place" (overwriting the original matrix) in this example is easy: it involves swapping 3 pairs of elements: 1 and 3, 2 and 6, and 5 and 7. Elements 0, 4, and 8 do not need to be moved.

It is a bit more tricky when the matrix is not square. For example, the matrix:

    12 58 23
    81 74 96

is stored as { 12, 58, 23, 81, 74, 96 }. Its transpose is:

    12 81
    58 74 
    23 96

and is stored as: { 12, 81, 58, 74, 23, 96 }. This also requires 3 swaps. (See example 1 below.)

Given M and N, return the minimum number of swaps necessary to take the transpose of a matrix of that size in place.

Definition

Notes

Constraints

Examples