mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 16:36:41 +08:00
30 lines
973 B
Markdown
Executable File
30 lines
973 B
Markdown
Executable File
# [342. Power of Four](https://leetcode.com/problems/power-of-four/)
|
||
|
||
|
||
## 题目
|
||
|
||
Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
|
||
|
||
**Example 1:**
|
||
|
||
Input: 16
|
||
Output: true
|
||
|
||
**Example 2:**
|
||
|
||
Input: 5
|
||
Output: false
|
||
|
||
**Follow up**: Could you solve it without loops/recursion?
|
||
|
||
## 题目大意
|
||
|
||
给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。
|
||
|
||
|
||
## 解题思路
|
||
|
||
- 判断一个数是不是 4 的 n 次方。
|
||
- 这一题最简单的思路是循环，可以通过。但是题目要求不循环就要判断，这就需要用到数论的知识了。
|
||
- 证明 `(4^n - 1) % 3 == 0`，(1) `4^n - 1 = (2^n + 1) * (2^n - 1)`(2) 在任何连续的 3 个数中 `(2^n-1)`，`(2^n)`，`(2^n+1)`，一定有一个数是 3 的倍数。`(2^n)` 肯定不是 3 的倍数，那么 `(2^n-1)` 或者 `(2^n+1)` 中一定有一个是 3 的倍数。所以 `4^n-1` 一定是 3 的倍数。
|