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 anint
. \$\endgroup\$BigInteger
as an array index or a size for an array. You'd have to convert toint
first. This is an interesting problem, but you should suggest a more feasible input size, e.g. \$10^9\$. \$\endgroup\$