0 added
0 removed
Original
2026-01-01
Modified
2026-02-21
1
<p><a>#статьи</a></p>
1
<p><a>#статьи</a></p>
2
<ul><li>28 ноя 2022</li>
2
<ul><li>28 ноя 2022</li>
3
<li>0</li>
3
<li>0</li>
4
</ul><h2>Задача: можно ли представить число степенью тройки</h2>
4
</ul><h2>Задача: можно ли представить число степенью тройки</h2>
5
<p>Решаем задачи, которые дают программистам на собеседованиях в IT‑компаниях. Сегодня пытаемся понять, можно ли представить число степенью тройки.</p>
5
<p>Решаем задачи, которые дают программистам на собеседованиях в IT‑компаниях. Сегодня пытаемся понять, можно ли представить число степенью тройки.</p>
6
<p>Иллюстрация: Polina Vari для Skillbox Media</p>
6
<p>Иллюстрация: Polina Vari для Skillbox Media</p>
7
<p>Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.</p>
7
<p>Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.</p>
8
<p><strong>Условие.</strong>Дано целое число<strong>n</strong>. Нужно вернуть<strong>true</strong>, если его можно представить в виде степени числа 3. В противном случае необходимо вернуть<strong>false</strong>.</p>
8
<p><strong>Условие.</strong>Дано целое число<strong>n</strong>. Нужно вернуть<strong>true</strong>, если его можно представить в виде степени числа 3. В противном случае необходимо вернуть<strong>false</strong>.</p>
9
<p>Пояснение: число<strong>n</strong>можно представить в виде степени числа 3, если существует целое число<strong>x</strong>, которое делает истинным уравнение вида<strong>n == 3^x</strong>.</p>
9
<p>Пояснение: число<strong>n</strong>можно представить в виде степени числа 3, если существует целое число<strong>x</strong>, которое делает истинным уравнение вида<strong>n == 3^x</strong>.</p>
10
Ввод: n = 27 Вывод: true Пояснение: 27 = 3^3 Ввод: n = 0 Вывод: false Пояснение: нет такого x, которое бы удовлетворяло уравнению 3^x = 0 Ввод: n = -1 Вывод: false Пояснение: нет такого x, которое бы удовлетворяло уравнению 3^x = (-1)<p>Решить эту задачу самостоятельно и на разных языках программирования можно на <a>LeetCode</a>. Наше решение взято из телеграм-канала Сергея<a>Cracking code interview</a>.</p>
10
Ввод: n = 27 Вывод: true Пояснение: 27 = 3^3 Ввод: n = 0 Вывод: false Пояснение: нет такого x, которое бы удовлетворяло уравнению 3^x = 0 Ввод: n = -1 Вывод: false Пояснение: нет такого x, которое бы удовлетворяло уравнению 3^x = (-1)<p>Решить эту задачу самостоятельно и на разных языках программирования можно на <a>LeetCode</a>. Наше решение взято из телеграм-канала Сергея<a>Cracking code interview</a>.</p>
11
<p><strong>Решение</strong></p>
11
<p><strong>Решение</strong></p>
12
<p><strong>Первый вариант.</strong>Самый простой способ определить, можно ли представить число<strong>n</strong>степенью числа<strong>b</strong>, - это продолжать делить<strong>n</strong>на <strong>b</strong>до тех пор, пока остаток от деления равен 0. Если он не равен 0, значит, число нельзя представить в виде степени числа<strong>b</strong>.</p>
12
<p><strong>Первый вариант.</strong>Самый простой способ определить, можно ли представить число<strong>n</strong>степенью числа<strong>b</strong>, - это продолжать делить<strong>n</strong>на <strong>b</strong>до тех пор, пока остаток от деления равен 0. Если он не равен 0, значит, число нельзя представить в виде степени числа<strong>b</strong>.</p>
13
<p>Это верно, потому что мы можем записать число<strong>n</strong>так:</p>
13
<p>Это верно, потому что мы можем записать число<strong>n</strong>так:</p>
14
n = b^x n = b × b × ... × b<p>Поэтому, чтобы решить нашу задачу, мы должны поделить число<strong>n</strong>на <strong>b</strong>ровно<strong>x</strong>раз и в результате получить 1. При этом на одном шаге деления остаток от деления должен быть равен 0.</p>
14
n = b^x n = b × b × ... × b<p>Поэтому, чтобы решить нашу задачу, мы должны поделить число<strong>n</strong>на <strong>b</strong>ровно<strong>x</strong>раз и в результате получить 1. При этом на одном шаге деления остаток от деления должен быть равен 0.</p>
15
<p>Вот как этот алгоритм будет реализован на Java:</p>
15
<p>Вот как этот алгоритм будет реализован на Java:</p>
16
public boolean isPowerOfThree(int n) { if (n < 1){ return false; } while (n % 3 == 0){ n /= 3; } return n == 1; }<p><strong>Второй вариант.</strong>В другом варианте решения мы будем использовать ограничения языка Java. В нём целые числа представлены типом int, который занимает 4 байта и может принимать максимальное значение - 2147483647.</p>
16
public boolean isPowerOfThree(int n) { if (n < 1){ return false; } while (n % 3 == 0){ n /= 3; } return n == 1; }<p><strong>Второй вариант.</strong>В другом варианте решения мы будем использовать ограничения языка Java. В нём целые числа представлены типом int, который занимает 4 байта и может принимать максимальное значение - 2147483647.</p>
17
<p>Теперь, зная ограничения для целых чисел в Java, мы можем ограничить максимальную степень числа 3. В нашем случае она будет равна 1162261467 = 3^19, а следующая будет уже 3486784401 = 3^20, что выходит за рамки типа int.</p>
17
<p>Теперь, зная ограничения для целых чисел в Java, мы можем ограничить максимальную степень числа 3. В нашем случае она будет равна 1162261467 = 3^19, а следующая будет уже 3486784401 = 3^20, что выходит за рамки типа int.</p>
18
<p>Получается, что число<strong>n </strong>- это одна из степеней числа 3: 3^0, 3^1, … , 3^19. А число 3 - простое, следовательно, любая степень числа 3 делится только на степени тройки: 3^0, 3^1, … , 3^19.</p>
18
<p>Получается, что число<strong>n </strong>- это одна из степеней числа 3: 3^0, 3^1, … , 3^19. А число 3 - простое, следовательно, любая степень числа 3 делится только на степени тройки: 3^0, 3^1, … , 3^19.</p>
19
<p>Поэтому всё, что нам нужно сделать, - это найти остаток от деления числа 3^19 на <strong>n</strong>. Если он равен 0, значит, число можно представить в виде степени числа 3.</p>
19
<p>Поэтому всё, что нам нужно сделать, - это найти остаток от деления числа 3^19 на <strong>n</strong>. Если он равен 0, значит, число можно представить в виде степени числа 3.</p>
20
public boolean isPowerOfThree(int n) { return n > 0 && 1162261467 % n == 0; }<p><strong>Результаты</strong></p>
20
public boolean isPowerOfThree(int n) { return n > 0 && 1162261467 % n == 0; }<p><strong>Результаты</strong></p>
21
<p><strong>Временная сложность:</strong>O(log(n)) - так как мы перебирали все степени числа<strong>n</strong>. А во втором варианте - O(1), так как мы проводим одно вычисление.</p>
21
<p><strong>Временная сложность:</strong>O(log(n)) - так как мы перебирали все степени числа<strong>n</strong>. А во втором варианте - O(1), так как мы проводим одно вычисление.</p>
22
<p><strong>Ёмкостная сложность:</strong>O(1) - нам нужно заранее определённое количество места в памяти (максимальный размер памяти - размер числа<strong>n</strong>).</p>
22
<p><strong>Ёмкостная сложность:</strong>O(1) - нам нужно заранее определённое количество места в памяти (максимальный размер памяти - размер числа<strong>n</strong>).</p>
23
<a><b>Бесплатный курс по Python ➞</b>Мини-курс для новичков и для опытных кодеров. 4 крутых проекта в портфолио, живое общение со спикером. Кликните и узнайте, чему можно научиться на курсе. Смотреть программу</a>
23
<a><b>Бесплатный курс по Python ➞</b>Мини-курс для новичков и для опытных кодеров. 4 крутых проекта в портфолио, живое общение со спикером. Кликните и узнайте, чему можно научиться на курсе. Смотреть программу</a>