Số hoàn hảo — Leetcode 507

Liên kết vấn đề ban đầu:https://leetcode.com/problems/perfect-number/

Trong bài toán này, chúng ta được yêu cầu xác định xem một số nguyên n đã cho có phải là một số hoàn hảo hay không, được định nghĩa là một số nguyên bằng tổng tất cả các ước dương của nó (ngoại trừ chính n).

Cách trực quan nhất để thực hiện việc này là lặp từ 2 cho đến n/2 và theo dõi tổng đang chạy. Tuy nhiên, không có gì đáng ngạc nhiên, điều này đưa ra ngoại lệ vượt quá giới hạn thời gian đối với số lượng lớn.

Vì vậy, tôi đã nghĩ ra một giải pháp nhanh hơn bởi vì về mặt toán học, khi chúng ta tìm một thừa số, luôn có một thừa số khác tương ứng với nó và cũng phải là một phần của tổng (ví dụ: nếu n = 28 và chúng ta bắt đầu từ 2, thì 28 / 2 = 14 cũng phải là một hệ số và chúng ta có thể giảm một nửa số vòng lặp theo cách này vì chúng ta có thể thu hẹp khoảng cách nhanh hơn). Đây là giải pháp được chấp nhận mà tôi đã đưa ra:

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;
    }
}