No extra space xor method for rotation


  • 0
    N

    Here is a trick for swap two variable without extra space:

    a = a ^ b;
    b = a ^ b; // a ^ b ^ b = a
    a = a ^ b; // a ^ b ^ a = b
    

    Thus we can implement it for 4 elements, such as:

    private void counterClockwiseRotate(int a, int b, int c, int d) {
            a = a ^ b;
            b = b ^ c;
            c = c ^ d;
            d = a ^ b ^ c ^ d;  // a
            a = a ^ d;          // b
            b = b ^ a;          // c
            c = c ^ b;          // d
        }
    
        private void clockwiseRotate(int a, int b, int c, int d) {
            c = c ^ b;
            b = b ^ a;
            a = a ^ d;
            d = a ^ b ^ c ^ d;   // c
            c = c ^ d;           // b
            b = b ^ c;           // a
            a = a ^ b;           // d
        }
    

    Thus we can use it for our rotation:

        public static void rotate(int[][] matrix) {
            int n = matrix.length;
            for (int i = 0; i < n/2; i++) {
                for (int j = i; j < n-1-i; j++) {
                    matrix[n-1-i][n-1-j] = matrix[n-1-i][n-1-j] ^ matrix[j][n-1-i];
                    matrix[j][n-1-i] = matrix[j][n-1-i] ^ matrix[i][j];
                    matrix[i][j] = matrix[i][j] ^ matrix[n-1-j][i];
                    matrix[n-1-j][i] = matrix[i][j] ^ matrix[j][n-1-i] ^ matrix[n-1-i][n-1-j] ^ matrix[n-1-j][i];  
                    matrix[n-1-i][n-1-j] = matrix[n-1-i][n-1-j] ^ matrix[n-1-j][i];           
                    matrix[j][n-1-i] = matrix[j][n-1-i] ^ matrix[n-1-i][n-1-j];           
                    matrix[i][j] = matrix[i][j] ^ matrix[j][n-1-i];        
                }
            }
        }    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.