Building a matrix by applying XOR rules

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);
}
}
• m can't be $10^{18}$, as that's too big for an int. – mdfst13 Oct 14 '16 at 17:40
• The problem will still give time out even if I use BigInteger for m and n – Lokesh Pandey Oct 14 '16 at 17:41
• 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$. – mdfst13 Oct 14 '16 at 17:44
• 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 – Lokesh Pandey Oct 14 '16 at 17:48
• @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. – Robert Snyder Oct 14 '16 at 17:51

• 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;

• 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. – Lokesh Pandey Oct 14 '16 at 19:25
• @Lokesh OK. read it as $a_{i+k}$ instead. The logic stays the same. – vnp Oct 14 '16 at 19:28
• I am sorry I don't know how the logic stays the same will you help me with an example here – Lokesh Pandey Oct 14 '16 at 19:30
• As far as I am getting you you have put the xor operation from last value and then shifted it . Is it ? – Lokesh Pandey Oct 14 '16 at 20:39
• what is k here ? – Lokesh Pandey Oct 16 '16 at 8:01