Power of two check
Easy TimeO(1) SpaceO(1)
The powers of two are 1, 2, 4, 8, 16, 32 and so on, each twice the one before. Given a number, decide whether it is one of them. 1 counts, being two to the power of zero; 0 does not, and neither does any negative number.
Examples
Example 1
- Input
- numbers = [1, 3, 16, 18, 64]
- Output
- 1, 16 and 64 are powers of two; 3 and 18 each carry a second 1 in binary.
[[1,true],[3,false],[16,true],[18,false],[64,true]]
Example 2
- Input
- numbers = [0, -8, 2]
- Output
[[0,false],[-8,false],[2,true]]0and-8are ruled out before anything is counted, however tidy8looks.
The Code
function isPowerOfTwo(n) {
if (n <= 0) return false;
const mask = n - 1;
return (n & mask) === 0;
}
function classify(numbers) {
const out = [];
for (let i = 0; i < numbers.length; i++) {
out.push([numbers[i], isPowerOfTwo(numbers[i])]);
}
return out;
}
classify([1, 3, 16, 18, 64]);Done