23.10.2023
342. Power of Four easy
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/379
Problem TLDR
Is n == x^4
?
Intuition
There are several ways to solve this. We need to look at the bit representation of some examples, there are an even number of trailing zeros and always just a single 1
bit:
// 4 100
// 16 10000
// 64 1000000
Approach
if (n == 1) true else if (n == 0) false
else n % 4 == 0 && isPowerOfFour(n / 4)
Bit shift approach:
var x = n
var count = 0
while (x > 0 && x and 1 == 0) {
x = x shr 1
count++
}
return x == 1 && count % 2 == 0
Bit mask approach:
n > 0 && (n and (n - 1)) == 0 && (n and 0b0101_0101_0101_0101__0101_0101_0101_0101 != 0)
Use Kotlin countTrailingZeroBits
. Or do a Binary Search if you write that algorithm by hand:
unsigned int c = 32; // c will be the number of zero bits on the right
v &= -signed(v);
if (v) c--;
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;
Complexity
Time complexity:
O(1), for bit mask solutionSpace complexity:
O(1)
Code
fun isPowerOfFour(n: Int): Boolean = n > 0 &&
(n and (n - 1)) == 0 && n.countTrailingZeroBits() % 2 == 0