A power of LeetCode. 342 4

This is the 27th day of my participation in the August Genwen Challenge.More challenges in August

Title description:

342.4 Powers-force buckle (LeetCode) (leetcode-cn.com)

Given an integer, write a function to determine whether it is a power of 4. If so, return true; Otherwise, return false.

The integer n is a power of 4. There is an integer x such that n==4xn ==4 ^xn==4x

Example 1:

Input: n = 16 Output: trueCopy the code

Example 2:

Input: n = 5 Output: falseCopy the code

Example 3:

Input: n = 1 Output: trueCopy the code

Tip:

• 
  $-2^{31} <= n <= 2^{31} – 1$

Advanced:

Can you do this without using loops or recursion?

Thought analysis

In the bottom formula

In Leetcode.326 powers of 3 we have already solved similar problems using the base change formula.

Here is another excerpt from the analytic process of the base change formula.

N =4x n=4^x n=4x x= log4nx= log4nx= log104log10nx=\frac{log_{10} 4}{log_{10} n} x=log10nlog104

If n is a power of four, then log base four nlog base four nlog base four must be an integer, X =log104log10nx=\frac{log_{10} 4}{log_{10} n} x=log10nlog104, just check whether log4nlog_4 nlog4n is an integer.

Similarly, this formula can be generalized to powers of n.

AC code

class Solution {
    fun isPowerOfThree(n: Int): Boolean {
        
       / / k power
        val k = 4
        val a = Math.round(Math.log(n.toDouble()) / Math.log(k.toDouble()))
        val pow = Math.pow(k.toDouble(), a.toDouble()).toLong()
        return n > 0 && pow == n.toLong()

    }
}

Copy the code

Mathematics method

The same solution we used in Leetcode.326 powers of 3.

N =4xn=4^xn=4x = n=4 * 4 * 4 * 4

So if n is a power of 4, then n divided by 4 all the way must be equal to 1

AC code

class Solution {
    fun isPowerOfFour(n: Int): Boolean {
         if (n < 1) {
            return false
        }

        var sum=n
        while(sum%4= =0) {
            sum/=4
        }
        return sum == 1}}Copy the code

conclusion

Powers of 2, powers of 3, powers of 4, some of the methods are universal, such as mathematical methods, such as the base change formula.

After looking at the solution of the problem, I found that there are two clever solutions to the problem, binary method and the method of taking the properties of the model, because I did not think of the method at the beginning, I will not paste the code, and then see if I can solve it when I brush it.

reference

Powers of 4 – Powers of 4 – Force buckle (LeetCode) (leetcode-cn.com)

Leetcode.326 power of 3 (juejin.cn)