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);
 }
}

• mdfst13: m can't be \10ドル^{18}\,ドル as that's too big for an int.
• Lokesh Pandey: The problem will still give time out even if I use BigInteger for m and n
• mdfst13: You can't use BigInteger as an array index or a size for an array. You'd have to convert to int first. This is an interesting problem, but you should suggest a more feasible input size, e.g. \10ドル^9\$.
• Lokesh Pandey: I have solved this problem using BigInteger too. for(BigInteger i = BigInteger.valueOf(0); i.compareTo(m.subtract(BigInteger.valueOf(1))) <= 0; i = i.add(BigInteger.ONE)) xor[i.intValue()] = scan.nextBigInteger(); But this one also gave me time out. I am trying to find the relation between matrix rows since there is a xor operation so I think may be some of their properties might help
• Robert Snyder: @mdfst13 I don't believe the OP can make the size feasible as it appears to be from a programming challenge website meaning that the stipulations (as strange as they may be) are out of his control.

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;
  

• Lokesh Pandey: Nope if the a b c d e f are the inputs so the second row will be a^b b^c c^d d^e e^f f^a And the next row will be a^c b^d c^e d^f e^a and f^b. But I have found an interesting case for m=n , m>n and m<n . I guess binomial coefficient can help me to solve this problem more efficiently.
• vnp: @Lokesh OK. read it as \$a_{i+k}\$ instead. The logic stays the same.
• Lokesh Pandey: I am sorry I don't know how the logic stays the same will you help me with an example here
• Lokesh Pandey: As far as I am getting you you have put the xor operation from last value and then shifted it . Is it ?
• Lokesh Pandey: what is k here ?