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

Первый вариант. Самый простой способ определить, можно ли представить число 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;
  }