342. Power of Four in Leetcode

go-leetcode-342.go

/**
342. Power of Four
A code is realy simple but hard to realize the concept.
There's a magic mask to handle it, and it is also the best solution in leetcode.
Besides, I don't want to mention a brutal force solution with loop neither.

Here I use simple concept to explain it, and can help you memorize when you interview.

The problem asks us solve problem w/o loops/recursion 
Intuitively, 4^n is 2^n; on the contrary, 2^n is not alwasy 4^n only when 

    2^m = 4^n
    2^m = 2^(2n), m = 2n, m belongs even
        
Secondly,how do we tell from that n is even or odd w/o loop/recursion method ?
The equation can be expressed as bionomial distribution. 
Thanks xicilukou (https://leetcode.com/xicilukou)
        
    (a+b)^n = C(n,0)*a^n*b^0+C(n,1)*a^(n-1)*b^1+....+C(n,n)*a^0*b^n
        
As a result, 2^n = (3-1)^n = C(n,0)*3^n*(-1)^0+C(n,0)*3^(n-1)*(-1)^1+.....+C(n,n)*3^0*(-1)^n
                                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
we can get rid of 3 based terms by modul, and keep C(n,n)*3^0*(-1)^n. With the term, we can
distinguish from n beteen even and odd.
        
    if n is even, (2^n)%3 == 1
    otherwise, (2^n)%3 == -1 or 2           
        
Finally, we start with whether 2^n or not; then find out the power of four.
the time complexity is O(1)

**/
func isPowerOfFour(num int) bool {
    return num > 0 && (num & (num-1)) == 0 && num%3 == 1
}