classSolution{public:boolisPowerOfFour(unsignedn){// Why (4^n - 1) % 3 == 0?// (4^n - 1) = (2^n - 1)(2^n + 1) and 2^n - 1, 2^n, 2^n + 1 are// three consecutive numbers; among one of them, there must be a multiple// of 3, and that can't be 2^n, so it must be either 2^n - 1 or 2^n + 1.// Therefore, 4^n - 1 is a multiple of 3.returnn>0&&popcount(n)==1&&(n-1)%3==0;}};

1 2 3 4 5 6 7 8 910

classSolution{publicbooleanisPowerOfFour(intn){// Why (4^n - 1) % 3 == 0?// (4^n - 1) = (2^n - 1)(2^n + 1) and 2^n - 1, 2^n, 2^n + 1 are// three consecutive numbers; among one of them, there must be a multiple// of 3, and that can't be 2^n, so it must be either 2^n - 1 or 2^n + 1.// Therefore, 4^n - 1 is a multiple of 3returnn>0&&Integer.bitCount(n)==1&&(n-1)%3==0;}}

12345678

classSolution:defisPowerOfFour(self,n:int)->bool:# Why (4^n - 1) % 3 == 0?# (4^n - 1) = (2^n - 1)(2^n + 1) and 2^n - 1, 2^n, 2^n + 1 are# three consecutive numbers; among one of them, there must be a multiple# of 3, and that can't be 2^n, so it must be either 2^n - 1 or 2^n + 1.# Therefore, 4^n - 1 is a multiple of 3.returnn>0andn.bit_count()==1and(n-1)%3==0