Ugly Number

Условие

Определите, является ли заданное число n “уродливым” числом. Уродливые числа — это положительные числа, которые имеют только 2, 3 и 5 в качестве своих простых множителей.

Примеры

Input: n = 6

Output: true

Explanation: 6 = 2 × 3.

Input: n = 1

Output: true

Explanation: 1 не имеет простых множителей.

Input: n = 14

Output: false

Explanation: 14 = 2 × 7, 7 не является простым множителем 2, 3 или 5.

Решение

fun isUgly(n: Int): Boolean {
    if (n <= 0) return false // Уродливые числа только положительные
    var num = n
    
    // Делим на 2, 3 и 5, пока возможно
    while (num % 2 == 0) num /= 2
    while (num % 3 == 0) num /= 3
    while (num % 5 == 0) num /= 5
    
    // Если после деления мы получили 1, значит, n - уродливое число
    return num == 1
}

Временная сложность

O(log n), где n — значение входного числа, так как мы делим его на 2, 3 и 5.

Пространственная сложность

O(1), так как мы используем фиксированное количество переменных.