## Friday, May 13, 2016

### In-place convert matrix in specific order - GeeksforGeeks

In-place convert matrix in specific order - GeeksforGeeks
Write a code to convert a matrix in specific way without using extra space.

Input:
1 2 3
4 5 6
7 8 9

Output:
1 6 7
2 5 8
3 4 9
every even column in output matrix has elements of corresponding row in input matrix in opposite order.

void transformMatrix(int *A, int r, int c)
{
// Invert even rows
for (int i = 1; i < r; i = i + 2)
for (int j1 = 0, j2 = c - 1; j1 < j2; j1++, j2--)
swap(*(A + i*c + j1), *(A + i*c + j2));

// Rest of the code is from below post
int size = r*c - 1;
int t; // holds element to be replaced, eventually
// becomes next element to move
int next; // location of 't' to be moved
int cycleBegin; // holds start of cycle

bitset<HASH_SIZE> b; // hash to mark moved elements

b.reset();
b[0] = b[size] = 1;
int i = 1; // Note that A[0] and A[size-1] won't move
while (i < size)
{
cycleBegin = i;
t = A[i];
do
{
// Input matrix [r x c]
// Output matrix 1
// i_new = (i*r)%(N-1)
next = (i*r)%size;
swap(A[next], t);
b[i] = 1;
i = next;

while (i != cycleBegin);

// Get Next Move (what about querying
// random location?)
for (i = 1; i < size && b[i]; i++)
;
}
}