Is anybody can point out what is wrong with my solution?


  • 0
    J
    public void setZeroes(int[][] matrix) {
        long zero_rows = 0, zero_columns = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    zero_rows |= (1 << i);
                    zero_columns |= (1 << j);
                }
            }
        }
        
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (((zero_rows >> i) & 1) > 0 || ((zero_columns >> j) & 1) > 0) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
    

    I didn't pass the case 152.

    151 / 154 test cases passed.

    But there are only 50 rows and 51 columns in this case.

    Is there anybody can help me with this problem?

    Thanks!


  • 1
    D

    First of all, nice solution! Although I think you are aware of that it only works for matrix with certain size limitation.


    Then, although you use "long" specifier for zero_rows and zero_columns, there are two things to watch out here.

    1. long is not guaranteed to have 64 bit length, it is only true for 64-bit system. Therefore using long long instead of long is safer and more compatible.

    2. this statement is actually harming you even if you are working on 64-bit system:

      "zero_rows |= (1 << i);"

      To be specific, immediate numbers will be interpreted as int by default, and shifting an int by more than 32 is undefined behavior. Therefore 1 << 50 may well end not to be 2^49 as you thought.

      That being said, if you still want to use this solution to pass the test, try use (1LL << i) instead, while you put letters "LL" after 1 to indicate it's a "long long".

  • 0
    J

    Hi dragonmigo,

    Thank you for answering my question.

    You are right! The problem is that I used (1 << i) instead of (1L << i). So when the number of rows or columns is larger than 32, it'll not correct any more.

    I changed my code as following:

    zero_rows |= (1L << i);
    zero_columns |= (1L << j);

    Then it passed the case #152. Although this solution won't pass the larger case # 156, which has 154 columns.

    I'm not sure about how long type actually works in JVM. I'll look it up in java document.

    Thanks!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.