Дано: целое число n, верните true, если оно является степенью двойки. В противном случае возвращается false.
Пример 1:
Дано: n = 1
Выход: true
Пример 2:
Дано: n = 16
Выход: true
Пример 3:
Дано: n = 3
Выход: false
Ограничения:
-2^31 <= n <= 2^31 - 1
Решения:
1) Наивный подход
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
if n <= 0:
return False
if n == 1:
return True
while (n % 2 == 0):
n /= 2
return n == 1
Отсекаем ненатуральные числа, и циклом делим числом на 2, проверяем, что в конце получаем целочисленное значение.
Временная сложность: O(logn)
Пространственная сложность: O(1)
2) Использование свойства логарифма:
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n>0 and log2(n) == int(log2(n))
Используем библиотеку math для вычисления логарифма, если он целочисленный возвращаем true
Временная сложность: O(logn)
Пространственная сложность: O(1)
3) использование двоичной формы представления:
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n>0 and n&(n-1)==0
Натуральное число, представленное степенью двойки, имеет в своей двоичной записи одну единицу
Например:
n: 10000000, 01000000, 00100000, ..., 00000001
Что будет, если от такого числа отнимем единицу?
n-1: 01111111, 00111111, 00011111, ..., 00000000
Теперь, взяв and между n и n-1, мы получим все нули в двоичной записи.
(n & (n-1) == 0)
Временная сложность: O(1)
Пространственная сложность: O(1)
