Когда 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 здесь.

Ссылка на другие вопросы по программированию —
Найти максимальную прибыль при планировании заданий
Преобразование двоичного числа в связанном списке в целое число
Найти, сколько воскресений выпало на первое число месяца в данном году