i think if each row and each column is half ones or half zeros (or with an extra 1/0 when odd length) then it is impossible for there to be more or less than 2 distinct rows/columns. therefore those checks are redundant

Shouldn't the time complexity be O(n)? After all, all the pre-checks are linear, and in order to find the ideal number of steps we just need to count the number of incorrectly placed rows or columns which is also linear. Can someone explain why is it O(n^2). Thanks a lot in advance.

Shouldn't 0xAAAAAAAA and 0x55555555 be swapped, because if it starts with zero, it should be checked with 0x55555555 and when it starts with 1, it should be checked with 0xAAAAAAAA....please correct me if I am wrong