LeetCode Entry

342. Power of Four

23.10.2023 easy 2023 kotlin

Is n == x^4?

342. Power of Four easy blog post substack image.png

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 solution

  • Space complexity: \(O(1)\)

Code


    fun isPowerOfFour(n: Int): Boolean = n > 0 &&
      (n and (n - 1)) == 0 && n.countTrailingZeroBits() % 2 == 0