Задача: можно ли представить число степенью тройки
2026-02-21 03:13 Diff
https://skillbox.ru/media/code/zadacha-mozhno-li-predstavit-chislo-stepenyu-troyki/

#статьи

  • 28 ноя 2022
  • 0

Задача: можно ли представить число степенью тройки

Решаем задачи, которые дают программистам на собеседованиях в IT‑компаниях. Сегодня пытаемся понять, можно ли представить число степенью тройки.

Иллюстрация: Polina Vari для Skillbox Media

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

Условие. Дано целое число n. Нужно вернуть true, если его можно представить в виде степени числа 3. В противном случае необходимо вернуть false.

Пояснение: число n можно представить в виде степени числа 3, если существует целое число x, которое делает истинным уравнение вида n == 3^x.

Ввод: n = 27 Вывод: true Пояснение: 27 = 3^3 Ввод: n = 0 Вывод: false Пояснение: нет такого x, которое бы удовлетворяло уравнению 3^x = 0 Ввод: n = -1 Вывод: false Пояснение: нет такого x, которое бы удовлетворяло уравнению 3^x = (-1)

Решить эту задачу самостоятельно и на разных языках программирования можно на LeetCode. Наше решение взято из телеграм-канала Сергея Cracking code interview.

Решение

Первый вариант. Самый простой способ определить, можно ли представить число n степенью числа b, — это продолжать делить n на b до тех пор, пока остаток от деления равен 0. Если он не равен 0, значит, число нельзя представить в виде степени числа b.

Это верно, потому что мы можем записать число n так:

n​ = b^x n = b × b × ... × b

Поэтому, чтобы решить нашу задачу, мы должны поделить число n на b ровно x раз и в результате получить 1. При этом на одном шаге деления остаток от деления должен быть равен 0.

Вот как этот алгоритм будет реализован на Java:

public boolean isPowerOfThree(int n) { if (n < 1){ return false; } while (n % 3 == 0){ n /= 3; } return n == 1; }

Второй вариант. В другом варианте решения мы будем использовать ограничения языка Java. В нём целые числа представлены типом int, который занимает 4 байта и может принимать максимальное значение — 2147483647.

Теперь, зная ограничения для целых чисел в Java, мы можем ограничить максимальную степень числа 3. В нашем случае она будет равна 1162261467 = 3^19, а следующая будет уже 3486784401 = 3^20, что выходит за рамки типа int.

Получается, что число n — это одна из степеней числа 3: 3^0, 3^1, … , 3^19. А число 3 — простое, следовательно, любая степень числа 3 делится только на степени тройки: 3^0, 3^1, … , 3^19.

Поэтому всё, что нам нужно сделать, — это найти остаток от деления числа 3^19 на n. Если он равен 0, значит, число можно представить в виде степени числа 3.

public boolean isPowerOfThree(int n) { return n > 0 && 1162261467 % n == 0; }

Результаты

Временная сложность: O(log(n)) — так как мы перебирали все степени числа n. А во втором варианте — O(1), так как мы проводим одно вычисление.

Ёмкостная сложность: O(1) — нам нужно заранее определённое количество места в памяти (максимальный размер памяти — размер числа n).

Бесплатный курс по Python ➞
Мини-курс для новичков и для опытных кодеров. 4 крутых проекта в портфолио, живое общение со спикером. Кликните и узнайте, чему можно научиться на курсе. Смотреть программу