Building a matrix by applying XOR rules

Question

There is a matrix of \$m\$ rows and \$n\$ columns where each row is filled gradually. Given the first row of the matrix we can generate the elements in the subsequent rows using the formula:

$$\begin{align} a_{i,j} =&\ a_{i-1,j} \oplus a_{i-1,j+1}\quad\forall j:0\le j\le n-2 \\ a_{i,n-1} =&\ a_{i-1,n-1} \oplus a_{i-1,0} \end{align}$$

Each row is generated one by one, from the second row through the last row. Given the first row of the matrix, find and print the elements of the last row as a single line of space-separated integers.

For example, input as \$4 \space 2\$ (4 is the number of columns and 2 is the row which we are supposed to find):

• \$6 \space 7 \space 1 \space 3\$ (1st row input)
• 6^7 = 1
• 7^1 = 6
• 1^3 = 2
• 3^6 = 5

\$1 \space 6 \space 2 \space 5\$ are the final row output. Now, how could I optimise my program if the value of \$n\$ is like pow(10,5) and \$m\$ is like pow(10,18)?

import java.util.Scanner;
class XorMatrixMain{
    public static void Xor_Array(int[] xor, int n){
        int num = xor[0];
        boolean bool = false;
        int last = 0;
        for(int j=0;j<n-1;j++){
            for(int i=0 ; i<xor.length ; i++){
                if(i<xor.length-1){
                    xor[i] = xor[i]^xor[i+1];
                }
                if(i==xor.length-1){
                    if(bool){
                        xor[i] = xor[i]^last;
                    }
                    else{
                        xor[i] = xor[i]^num;
                        bool = true;
                    }                       
                }
            }
            last = xor[0];
        }
        for(int i=0;i<xor.length;i++){
            System.out.print(xor[i]+" ");
        }
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        int n = scan.nextInt();
        int[] xor = new int[m];
        for(int i=0;i<m;i++){
            xor[i] = scan.nextInt();
        }
        Xor_Array(xor,n);
    }
}

Answer 1

• Time complexity is \$O(nm)\$. Obviously it is bound to TLE. There is an \$O(n)\$ solution, based on the following observations:

  • \$ x \oplus x = 0\$
  • \$ x \oplus y = y \oplus x\$

  Let's say your initial row is a b c d e f. The next row will be a^f b^a c^b d^c e^d f^e. The second next is more interesting: the first element is a^f ^ f^e = a^e, the second is a^f ^ b^a = b^f, etc.

  In general (prove it by induction), \$k\$'th row consists of \$a_i \oplus a_{i-k}\$ (where the last index is taken modulo n). Notice that the \$n\$'th row is all zeroes, and so are all the subsequent rows.

• The code is extremely hard to follow. num is only used once - may be not have it at all?

      last = xor[0];
  
      for(int i=0 ; i<xor.length ; i++){
          if(i<xor.length-1){
              xor[i] = xor[i]^xor[i+1];
          }
          if(i==xor.length-1){
              xor[i] = xor[i]^last;
          }
      }
  

  Notice that i == xor.length - 1 is true exactly once, at the predictable i, yet you test it at each iteration. Lift it out of the loop:

      last = xor[0];
      for(int i=0 ; i<xor.length - 1; i++){
          xor[i] = xor[i]^xor[i+1];
      }
      xor[i] = xor[i]^last;