หมายเลขที่สมบูรณ์แบบ — Leetcode 507

ลิงค์ปัญหาเดิม:https://leetcode.com/problems/perfect-number/

ในปัญหานี้ เราถูกขอให้พิจารณาว่าจำนวนเต็ม n ที่กำหนดเป็นจำนวนสมบูรณ์หรือไม่ โดยกำหนดให้เป็นจำนวนเต็มที่เท่ากับผลรวมของตัวหารที่เป็นบวกทั้งหมด (ไม่รวมตัว n เอง)

วิธีที่ง่ายที่สุดในการทำเช่นนี้คือการวนซ้ำจาก 2 ไปจนถึง n / 2 และติดตามผลรวมที่กำลังดำเนินอยู่ อย่างไรก็ตาม ไม่น่าแปลกใจที่สิ่งนี้ให้ข้อยกเว้นเกินเวลาที่กำหนดสำหรับตัวเลขจำนวนมาก

ดังนั้นฉันจึงคิดวิธีแก้ปัญหาที่เร็วกว่าได้ เพราะในทางคณิตศาสตร์ เมื่อเราพบตัวประกอบ มันมักจะมีตัวประกอบอื่นที่สอดคล้องกับตัวประกอบที่ควรเป็นส่วนหนึ่งของผลรวมเสมอ (เช่น ถ้า n = 28 และเราเริ่มจาก 2 แล้ว 28 / 2 = 14 ควรเป็นปัจจัยด้วย และเราสามารถลดจำนวนลูปลงครึ่งหนึ่งด้วยวิธีนี้ เนื่องจากเราสามารถปิดช่องว่างได้เร็วกว่า) นี่เป็นวิธีแก้ปัญหาที่ฉันยอมรับ:

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