Разбор задачи 326. Power of Three с Литкода

https://leetcode.com/problems/power-of-three/

Условие

Дано число n, вернитеtrue Если оно степень тройки. Иначе, верните false.

Число n степень тройки, если есть число x такое, что n == 3^x.

Пример 1:

Ввод: n = 27
Вывод: true
Explanation: 27 = 3^3

Пример 2:

Ввод: n = 0
Вывод: false
Объяснение: Нет x, чтобы 3^x = 0.

Пример 3:

Ввод: n = -1
Вывод: false
Объяснение: Нет x, чтобы 3^x = -1.

Ограничения:

-231 <= n <= 231 - 1

Дополнительно: Можешь ли ты это решить без циклов/рекурсии?

Решение

Обычное решение такое:

public class Solution {
    public bool IsPowerOfThree(int n) {
        while (n > 1)
        {
            if (n % 3 != 0)
            {
                return false;
            }
            n /= 3;
        }
        return n == 1;
    }
}

А есть ли необычное решение? Да, есть.

3 - это простое число (делится только на себя и на единицу).

Если представим, некую степень тройки, как:

3 * 3 * 3 * 3 * 3 * 3 * 3...

то увидим, что оно тоже делится только на степень 3. На 3, или на 3 * 3 (9), или на 3 * 3 * 3 (27), и т.д.

Диапазон значений у нас от int.MinValue до int.MaxValue. Понятно, что отрицательные числа и 0 нам не нужны. Итого, остается диапазон от единицы до int.MaxValue. Если мы найдем такую максимальную степень тройки (пусть будет называться она max), что входит в этот дипазон, то мы можем определить, является ли n степеню 3-ки так:

max % n == 0

Если n не будет степень 3, то max не будет делиться на неё.

Как найти этот max?

Узнаем степень 3, чтобы получить int.MaxValue:

var power = Math.Log(int.MaxValue, 3);

Мы узнали, такое x, что 3^x = int.MaxValue
Понятно, что это какое-то дробное число.
Отбросим дробную часть:

var power = Math.Truncate(Math.Log(int.MaxValue, 3))

Теперь возведем 3 в эту степень.

var max = Math.Pow(3, power);

Одно из решение такое:

public class Solution {
    public bool IsPowerOfThree(int n) {
        if (n <= 0)
        {
            return false;
        }
        var power = Math.Truncate(Math.Log(int.MaxValue, 3));
        var max = Math.Pow(3, power);
        return max % n == 0;
    }
}

Если кто не знал, то на Литкоде можно выводить в консоль. выведем max:

Console.WriteLine(max);

Получим 1162261467, если выведем power, то получим 19. Итак, максимальная степень тройки в диапазоне от 1 до int.MaxValue - это 3^19.

Итого, решение может быть в одну строчку.

public class Solution {
    private const int MaxPowerOf3 = 1162261467;
    public bool IsPowerOfThree(int n) {
        return n > 0 && MaxPowerOf3 % n == 0;
    }
}