The challenge: Given integers N and K (where 2 <= K <= N), find the highest value of A & B (i.e. A bitwise-AND B) such that 0 <= A < B <= N and (A & B) < K.
I've made my code and it runs perfect with visible cases but it fails with the hidden cases.
My Code:
function bitwiseAnd(N, K) {
// Write your code here
let arr = []
N = parseInt(N,10)
K = parseInt(K,10)
for(let a=1; a<N; a++){
for(let b=a+1; b<=N ; b++){
if(K>=0 && parseInt(a&b,10) < K && parseInt(a&b,10)>=0) arr.push(parseInt(a&b,10))
}
}
return Math.max(...arr)
}
i searched for a solution and i found this one.
Solution:
function bitwiseAnd(N, K) {
// Write your code here
var n = parseInt(N);
var k = parseInt(K);
var a = k - 1;
var b = (~a) & -(~a);
if ( (a | b) > n )
return(a - 1);
else
return(a);
}
However the solution's code is working good with all hidden test, i cannot understand how it works, as i'm not familiar with Bitwise operators.
is there any chance to get an explanation of this operators and how to use ?
Thanks in advance.
Here is a variant of your code that works:
function bitwiseAnd(N, K) {
let r = 0;
for(let a=1; a<N; a++) {
for(let b=a+1; b<=N; b++) {
if((a&b) < K) r = Math.max(r, a&b)
}
}
return r
}
console.log(bitwiseAnd(5,2)) // 1
console.log(bitwiseAnd(8,5)) // 4
console.log(bitwiseAnd(2,2)) // 0I've removed unnecessary parseInts and result checks. However, the only thing that was actually wrong with your code was the line Math.max(...arr).
The problem with that line is that it is not passing a reference to arr to the Math.max method. Instead, it is actually including all members of arr as arguments which will appear on the Javascript call stack. Normally, this would be fine. However, if you have hundreds of thousands of values in the array, the maximum call stack size will be exceeded and your code will fail to execute. This is why a hidden test case, which must have resulted in huge numbers of array members, caused hackerrank to reject your solution.
You've also posted a very interesting solution which does not use loops at all.
I've cleaned it up a little, and included it below:
function bitwiseAnd(n, k) {
let a = k-1
return (a | ~a & a+1) <= n ? a : a-1
}
console.log(bitwiseAnd(5,2)) // 1
console.log(bitwiseAnd(8,5)) // 4
console.log(bitwiseAnd(2,2)) // 0Note that the original code said & -(~a) instead of & a+1. The Two's complement method of negating a number is to flip all bits and add one to the result. Since the bitwise not ~ also means to flip all bits, the original code flips all bits, flips all bits again, and then adds one. This is therefore an obfuscation of simply doing a+1.
Here is an explanation of the thinking that must be behind that code:
Since the result of A & B must be less than K, the maximum number that might be the result will be K-1.
When we do the bitwise A & B, the result can only switch certain bits off, and cannot switch any bits on. Since A must be a smaller number than B, and since we can only switch bits of A off, the result of A & B thus cannot exceed the value of A.
Combining the two conclusions above, we can conclude:
A cannot exceed K-1 if our choice of B will preserve all bits of A.So, let's see if we can set A to K-1 and find a value of B which will preserve all bits in A.
The first value greater than A that will preserve all bits of A will be the result of setting the least significant bit that is currently unset.
For example, if A = 101, the next value of B that will preserve all bits of A after doing A & B is 111.
In order to locate the position of the least significant unset bit, we can do ~A & A+1. For the example where A is 101, ~A & A+1 is 010. Essentially, ~A & A+1, no matter what the value of A, will always return a binary sequence containing exactly one set bit.
The reason this works is that ~A acts as a mask that will only allow the result of ~A & A+1 to contain bits which were unset in A. When we do A+1, the first bit that will be set for the first time in A will be the least significant unset bit, and no other bits will be set for the first time.
For example: if A = 101, ~A = 010, A+1 = 110, and so ~A & A+1 = 010 & 110 = 010. That 1 in the answer is the position of the least significant unset bit in A.
If we do a bitwise OR, we can use this result to calculate the first higher value of B which will preserve all bits of A. Thus B = A | ~A & A+1. Therefore, we can see in the runnable code snippet above that if we find that (a | ~a & a+1) <= n, we know that the value of a = k-1 will work and we can return this as the answer.
But, what if that value of B that exceeds N? We will need to find the next-best answer.
Since we tried A = K-1, and since the question states K <= N, this means A must have been an odd number (i.e. the least significant bit was set). This is because if A was even, we'd have attempted the value B = A + 1, and B could not have exceeded N since K <= N and A = K-1.
So, since our earlier attempt failed when we tried A = K-1, we know we can't go higher than A to find a value of B that works when A = K-1.
But, if we set A = K-2, and since we know K-1 was odd, this means K-2 is even. This means that we can have A = K-2 and B = K-1, and A & B = K-2. The result of the function is therefore K-2.
The code could therefore perhaps be more clearly written as:
function bitwiseAnd(n, k) {
let a = k-1
return (a | ~a & a+1) <= n ? k-1 : k-2
}
console.log(bitwiseAnd(5,2)) // 1
console.log(bitwiseAnd(8,5)) // 4
console.log(bitwiseAnd(2,2)) // 0The bottom line is that we don't need any loops, because there is always an answer where A = K-1 and B is more than one higher than A, or where A = K-2 and B = K-1.
But, there is an improvement we can make...
So far, we've explained the thinking behind the solution you posted. That solution, however, is more complicated than it needs to be.
If we want to take A and set the least-significant unset bit, we can simply do A | A+1.
This means a simpler solution would be:
function bitwiseAnd(n, k) {
let a = k-1
return (a | a+1) <= n ? k-1 : k-2
}
console.log(bitwiseAnd(5,2)) // 1
console.log(bitwiseAnd(8,5)) // 4
console.log(bitwiseAnd(2,2)) // 0And, if we really want to code-golf the solution, we can substitute out the variable a, and take advantage of Javascript coercing true/false to 1/0 and do:
function bitwiseAnd(n, k) {
return --k-((k++|k)>n)
}
console.log(bitwiseAnd(5,2)) // 1
console.log(bitwiseAnd(8,5)) // 4
console.log(bitwiseAnd(2,2)) // 0