Given a matrix of size NxN. Rows and Columns are numbered from 0 to N-1. jth column of ith row contains i xor j. In other words, Matrix[i][j] = i ^ j where 0 ? i,j < N. Your task is to find the maximum value occurring in this matrix and the count of its occurrence.
While my approach was
(l..r).each do |i|
(i..r).each do |j|
if (i ^ j > max)
max = i ^ j
end
end
end
I saw this code which says it according to everyone is not quadratic is finding it in linear time.
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long N;
long max = 1L;
long count = 1L;
long bitN ;
StringBuilder sb = new StringBuilder(4*T);
line = br.readLine();
N = Long.parseLong(line);
{
bitN = 1L << getBits(N-1);
max = (bitN - 1);
count = (bitN == N) ? bitN :(N -(bitN>>1))<<1 ;
sb.append(max);
sb.append(" ");
sb.append(count);
sb.append("\n");
}
System.out.println(sb.toString());
}
private static int getBits(long x){
int count = 0;
while(x > 0){
x = x>>1;
count++;
}
return count;
}
}
What i'm unable to understand is how is this actually
bitN = 1L << getBits(N-1);
max = (bitN - 1);
count = (bitN == N) ? bitN :(N -(bitN>>1))<<1 ;
able to get the desired result. If anyone of you could just give me basic of this algorithm in simple terms so that i can understand this
Make a table of N versus max and count:
N max count how
1 0 1 0^0
2 1 2 0^1, 1^0
3 3 2 1^2, 2^1
4 3 4 1^2, 2^1, 0^3, 3^0
5 7 2 3^4, 4^3
6 7 4 3^4, 4^3, 2^5, 5^2
7 7 6 3^4, 4^3, 2^5, 5^2, 1^6, 6^1
8 7 8 3^4, 4^3, 2^5, 5^2, 1^6, 6^1, 0^7, 7^0
9 15 2 7^8, 8^7
.
.
The pattern is that, after N crosses a power of two, the max goes up and the count goes back to 2. This is because the bit patterns look like this:
3 = 0b011
4 = 0b100
.
.
7 = 0b0111
8 = 0b1000
bitN is the lowest bit set nowhere in 0..N-1 (so bitN = 8 when N = 8, and bitN = 16 when N = 9). The maximum XOR has all bits below bitN set, which is bitN - 1 by the logic of borrowing in grade-school subtraction. The count goes up two every time N increases by one except when bitN increases as well, when the count resets to two. The purpose of the ternary operator in computing count is to special case N = 1; the left branch is also taken when N is a greater power of two, but the other would work as well.