Perfekte Zahl – Leetcode 507

Ursprünglicher Problemlink:https://leetcode.com/problems/perfect-number/

Bei dieser Aufgabe müssen wir feststellen, ob eine gegebene ganze Zahl n eine vollkommene Zahl ist, die als ganze Zahl gleich der Summe aller ihrer positiven Teiler (ohne n selbst) definiert ist.

Der intuitivste Weg, dies zu tun, besteht darin, von 2 bis zu n / 2 zu schleifen und die laufende Summe zu verfolgen. Es überrascht jedoch nicht, dass dies eine Ausnahme bei Überschreitung des Zeitlimits für große Zahlen ergibt.

Also bin ich auf eine schnellere Lösung gekommen, denn mathematisch gesehen gibt es, wenn wir einen Faktor finden, immer einen anderen Faktor, der dazu gehört, der auch Teil der Summe sein sollte (z. B. wenn n = 28 und wir beginnen bei 2, dann 28 / 2 = 14 sollte auch ein Faktor sein und wir können die Anzahl der Schleifen auf diese Weise halbieren, da wir die Lücke schneller schließen können). Dies ist die akzeptierte Lösung, die ich mir ausgedacht habe:

class Solution {
    public boolean checkPerfectNumber(int num) {
        if (num == 1) {
            return false;
        }
        int sum = 1;
        int left = 2;
        int right = num / 2;
        while (left < right) {
            if (num % left == 0) {
                sum += left;
                sum += (num / left);
                right = num / left;
            }
            left++;
        }
        return sum == num;
    }
}