Когда Number N === Sum of its proper divisors
. Тогда это известно как Идеальное число. Пример:
Number = 28 Proper divisors of 28 = 1, 2, 4, 7, 14 Since, 1 + 2 + 4 + 7 + 14 = 28 It is a perfect number.
Любое число N
называется недостаточным, если сумма его делителей меньше N
, и избыточным, когда сумма превышает N
.
Мы напишем функцию checkNumber
с номером N
в качестве параметра импорта и вернем строку Идеально, Недостаточно или Изобильно на основе приведенного выше определения.
Реализация с использованием JavaScript:
Во-первых, нам нужно найти все делители заданного number
. Самый простой способ сделать это — проверить прямое деление всех чисел, меньших заданного number
, в итерации, и если остаток равен нулю, это один из моих делителей.
Пример:
const getDivisors = (number) => { const all_divs = []; for (let i=0; i<number; i++) { if (number % i === 0) { all_divs.push(i); } } return all_divs; }
Однако это наивный способ нахождения делителей, который может занять много времени, особенно когда заданное number
является значащим. Следовательно, временная сложность этого метода будет O(N)
, где N = number
.
Теперь мы знаем, что факторы всегда парные. Пример:
1 & 24 2 & 12 4 & 6
и так далее…
Таким образом, будет лучше выполнить итерацию до квадратного корня из заданного number
, а не до самого number
. Затем получите парные коэффициенты, используя num/i
, где i
— текущее число и коэффициент в итерации.
Реализация будет такой, как показано ниже:
const getDivisors = (number) => { const all_divs = []; for (let i = 1; i<=Math.sqrt(number);i++) { if (number % i == 0) { if (number/i == i) { all_divs.push(i); } else { all_divs.push(i); all_divs.push(number/i); } } } return all_divs; }
Это уменьшит временную сложность до O(SQRT(N))
, где N = number
.
Примечание: это, вероятно, не будет верно для случая, когда мы хотим найти делители для многих чисел. Как и в приведенном выше случае, мы хотим найти делители только для данного
number
. Однако, когда есть много чисел, для которых мы хотим найти делители. Тогда, вероятно, было бы лучше использовать один итерационный цикл для всех чисел и повторять до максимального числа этих чисел для более быстрого результата. Опять же, это можно протестировать, и это будет зависеть от варианта использования.
Я также проанализировал платформу leetcode, используя обе реализации, чтобы найти делители.
На изображении ниже показано, что первый способ занял 8324ms
, тогда как результаты были намного быстрее, когда те же тестовые случаи выполнялись вторым способом — 72 ms
.
Этот результат был ожидаем, поскольку мы уже знали, что временная сложность при использовании первого способа составляет O(N)
, а при использовании второго способа — O(SQRT(N))
.
Теперь, когда у нас есть все делители для данного number
. Давайте проверим, является ли это число Perfect
, Deficient
или Abundant
.
const checkNumber
= (number) => {
const all_divs = getDivisors(number);
let sum = 0;
for (let i=0; i<all_divs.length; i++) {
if (all_divs[i] !== num) {
sum = sum + all_divs[i];
}
}
if (sum === num) {
return 'Perfect';
}
if (sum < num) {
return 'Deficient';
}
return 'Abundant';
};
Мы перебираем делители и складываем их вместе.
- Когда sum == number
, это Идеально.
- Когда sum > number
, это Изобилие.
- Когда sum < number
, это Дефицит.
Вот и все.
Теперь аналогичная проблема на платформе leetcode здесь.
Ссылка на другие вопросы по программированию —
Найти максимальную прибыль при планировании заданий
Преобразование двоичного числа в связанном списке в целое число
Найти, сколько воскресений выпало на первое число месяца в данном году