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
versusmax
andcount
:The pattern is that, after
N
crosses a power of two, themax
goes up and thecount
goes back to2
. This is because the bit patterns look like this:bitN
is the lowest bit set nowhere in0..N-1
(sobitN = 8
whenN = 8
, andbitN = 16
whenN = 9
). The maximum XOR has all bits belowbitN
set, which isbitN - 1
by the logic of borrowing in grade-school subtraction. The count goes up two every timeN
increases by one except whenbitN
increases as well, when the count resets to two. The purpose of the ternary operator in computingcount
is to special caseN = 1
; the left branch is also taken whenN
is a greater power of two, but the other would work as well.