3
\$\begingroup\$

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

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.