CF 102697138 - Perfect Numbers

The problem asks us to examine one positive integer (n). We need to add up every positive divisor of (n) except (n) itself. If that sum equals (n), then (n) is a perfect number.

codeforcescompetitive-programming

CF 102697138 - Perfect Numbers

Rating: -
Tags: -
Solve time: 1m 28s
Verified: yes

Solution

Problem Understanding

The problem asks us to examine one positive integer (n). We need to add up every positive divisor of (n) except (n) itself. If that sum equals (n), then (n) is a perfect number. The output must first state whether this happens, using the exact required phrase, and then print the divisor sum. The archived problem is Gym 102697, problem 138, with a one-second limit and 256 MB of memory.

For example, when (n=28), the proper divisors are (1,2,4,7,14), whose sum is (28), so the output is PERFECT NUMBER followed by 28. For (n=48), the proper divisors sum to (76), so the output is NOT A PERFECT NUMBER followed by 76.

The statement does not give a small explicit upper bound in its displayed constraints. Instead, it guarantees that every value involved in the calculation fits in a Java int, so an implementation should not assume that a trial loop up to (n) is practical. A 32-bit signed integer can be as large as roughly (2.1\times10^9), and iterating through every integer up to such a value would require billions of divisibility checks. Even though the requested sum itself fits in the stated integer range, the algorithm still has to avoid scanning the whole interval.

There are several boundary cases that a direct implementation can mishandle. The first is (n=1). Its only divisor is (1), but that divisor is excluded because it is the number itself, so the proper-divisor sum is (0). The correct output is NOT A PERFECT NUMBER followed by 0. A careless implementation that initializes the sum with (1) for every input would incorrectly classify (1).

A second case is a prime number such as (n=7). Its only proper divisor is (1), so the answer is NOT A PERFECT NUMBER followed by 1. An implementation that only looks for divisor pairs and forgets the divisor (1) can produce an incorrect sum of zero.

A third case is a perfect square such as (n=36). Its divisor pair (6\times6) contains the same divisor twice, so (6) must be added only once. The proper-divisor sum is (1+2+3+4+6+9+12+18=55). If the square root is handled like an ordinary divisor pair, (6) is counted twice and the result becomes (61).

Finally, a genuine perfect number such as (n=6) has proper divisors (1,2,3), giving exactly (6). The correct output is PERFECT NUMBER followed by 6. This case catches implementations that accidentally exclude one of the divisors in a pair.

Approaches

The straightforward approach is to test every integer (d) from (1) through (n-1), check whether (d) divides (n), and add it when it does. This is correct because every proper divisor is considered exactly once. The problem is the number of checks. For an input near the largest value permitted by a signed Java int, this means roughly (2.1\times10^9) modulus operations, which is far beyond what a one-second competitive-programming solution can afford.

The useful structure is that divisors occur in pairs. If (d) divides (n), then (n/d) is also a divisor. For example, the divisors of (48) pair as (1,48), (2,24), (3,16), (4,12), and (6,8). When we only need proper divisors, the member equal to (n) must be excluded, but every other divisor can still be found through these pairs.

This means we only need to test candidate divisors up to (\sqrt n). Whenever (d) divides (n), we add (d) and its paired divisor (n/d). If (d) is exactly (\sqrt n), the two values are identical and must be added only once. We also need to avoid adding (n) itself, which happens when (d=1) and its paired divisor is (n).

The brute-force method works because it explicitly checks every possible proper divisor, but it fails because the search interval is as large as (n). The observation that divisors arrive in complementary pairs lets us replace an (O(n)) search with an (O(\sqrt n)) search. For a value around (2\times10^9), this reduces the number of divisor candidates from billions to only about 46,000.

Approach Time Complexity Space Complexity Verdict
Brute Force (O(n)) (O(1)) Too slow
Optimal (O(\sqrt n)) (O(1)) Accepted

Algorithm Walkthrough

  1. Read the integer (n) and initialize the proper-divisor sum to zero. Starting from zero is necessary because (1) is not a proper divisor when (n=1).
  2. Iterate (d) from (1) through (\lfloor\sqrt n\rfloor). We never need to examine a larger candidate directly because any divisor larger than (\sqrt n) is paired with a smaller divisor that we will encounter in the loop.
  3. Whenever (d) divides (n), compute the paired divisor (q=n/d). The pair ((d,q)) gives all divisors associated with this value of (d).
  4. Add (d) if (d<n). This condition is always true for (d\leq\sqrt n) except for the trivial case (n=1), but writing the condition explicitly makes the proper-divisor requirement clear.
  5. Add (q) if (q\neq d) and (q<n). The first condition prevents a perfect square from counting its square root twice, while the second condition prevents (n) itself from entering the proper-divisor sum.
  6. Compare the resulting sum with (n). Print PERFECT NUMBER when they are equal, otherwise print NOT A PERFECT NUMBER, followed by the sum on the second line.

Why it works

The invariant is that after processing every candidate divisor (d\leq\sqrt n), the running sum contains every proper divisor whose complementary divisor has already been reached, and contains each such divisor exactly once. Every divisor of (n) belongs to a pair ((d,n/d)) with one member at most (\sqrt n), so the loop eventually discovers every divisor. The condition (q\neq d) handles the only case where a pair collapses into one value, namely a perfect square. The condition (q<n) excludes (n) itself, leaving exactly the proper divisors. Thus the final sum is precisely the quantity required by the problem, so comparing it with (n) gives the correct classification.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n = int(input())

    divisor_sum = 0
    d = 1

    while d * d <= n:
        if n % d == 0:
            q = n // d

            if d < n:
                divisor_sum += d

            if q != d and q < n:
                divisor_sum += q

        d += 1

    if divisor_sum == n:
        print("PERFECT NUMBER")
    else:
        print("NOT A PERFECT NUMBER")

    print(divisor_sum)

if __name__ == "__main__":
    solve()

The loop begins at (1) because (1) is a divisor of every positive integer. For each successful divisibility test, q = n // d gives the complementary divisor without another search.

The condition d * d <= n is preferable to calculating a floating-point square root. It avoids rounding concerns and keeps the entire calculation in integer arithmetic. Python integers also remove any overflow concern, although the original statement guarantees that the relevant values fit in a Java int.

The two checks before adding a divisor are what enforce the definition precisely. When n = 48 and d = 1, the pair is (1, 48). The value 1 is added, while 48 is rejected because it is the number itself. When n = 36 and d = 6, the pair is (6, 6), so the first condition adds 6 and the second condition rejects it because q == d.

There is no need to store the divisors. We only need their sum, so a single accumulator is sufficient.

Worked Examples

For Sample 1, the input is 28. The divisor pairs discovered by the loop are shown below.

(d) (n/d) Added values Sum
1 28 1 1
2 14 2, 14 17
3 9 none 17
4 7 4, 7 28
5 not a divisor none 28

The loop stops after (d=5) because (6^2>28). The final sum is (28), so the number is perfect and the output is PERFECT NUMBER followed by 28. The trace demonstrates that every divisor pair is found while the number itself is excluded.

For Sample 2, the input is 48.

(d) (n/d) Added values Sum
1 48 1 1
2 24 2, 24 27
3 16 3, 16 46
4 12 4, 12 62
5 not a divisor none 62
6 8 6, 8 76

The loop stops after (d=6) because (7^2>48). The proper-divisor sum is (76), which differs from (48), so the output is NOT A PERFECT NUMBER followed by 76. This trace demonstrates why checking only up to the square root is sufficient: the larger divisors (24,16,12,8) are recovered as partners of (2,3,4,6).

Complexity Analysis

Measure Complexity Explanation
Time (O(\sqrt n)) At most (\lfloor\sqrt n\rfloor) candidate divisors are tested.
Space (O(1)) Only the input, loop variable, paired divisor, and running sum are stored.

For a value close to (2^{31}-1), (\sqrt n) is only about 46,341. That is small enough for the one-second limit, while an (O(n)) scan could require more than two billion iterations. The algorithm therefore changes the practical behavior of the solution rather than merely improving its constant factor.

Test Cases

import sys
import io

def solve_value(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout

    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    n = int(sys.stdin.readline())

    divisor_sum = 0
    d = 1

    while d * d <= n:
        if n % d == 0:
            q = n // d

            if d < n:
                divisor_sum += d

            if q != d and q < n:
                divisor_sum += q

        d += 1

    if divisor_sum == n:
        print("PERFECT NUMBER")
    else:
        print("NOT A PERFECT NUMBER")

    print(divisor_sum)

    result = sys.stdout.getvalue()

    sys.stdin = old_stdin
    sys.stdout = old_stdout

    return result

# Provided samples
assert solve_value("28\n") == "PERFECT NUMBER\n28\n", "sample 1"
assert solve_value("48\n") == "NOT A PERFECT NUMBER\n76\n", "sample 2"

# Minimum-size input
assert solve_value("1\n") == "NOT A PERFECT NUMBER\n0\n", "n = 1"

# Smallest perfect number
assert solve_value("6\n") == "PERFECT NUMBER\n6\n", "smallest perfect number"

# Perfect square, catches double-counting of sqrt(n)
assert solve_value("36\n") == "NOT A PERFECT NUMBER\n55\n", "perfect square"

# Prime number, catches incorrect handling of divisors
assert solve_value("7\n") == "NOT A PERFECT NUMBER\n1\n", "prime number"

# Large boundary value, checks that the O(sqrt(n)) loop remains practical
assert solve_value("2147483647\n") == "NOT A PERFECT NUMBER\n1\n", "large prime boundary"
Test input Expected output What it validates
1 NOT A PERFECT NUMBER / 0 Minimum input and exclusion of the number itself
6 PERFECT NUMBER / 6 Smallest perfect number
36 NOT A PERFECT NUMBER / 55 Square-root divisor is counted exactly once
7 NOT A PERFECT NUMBER / 1 Prime-number divisor handling
2147483647 NOT A PERFECT NUMBER / 1 Large boundary value and (O(\sqrt n)) performance

Edge Cases

For (n=1), the exact input is 1. The loop starts with (d=1), which divides (1), giving (q=1). The first condition rejects (d) because (d<n) is false, and the second condition rejects (q) because (q=d). The sum remains zero, so the output is NOT A PERFECT NUMBER followed by 0. This avoids the common mistake of treating (1) as its own proper divisor.

For a prime such as (n=7), the only divisor pair found is (1,7). The algorithm adds (1), rejects (7) because it equals (n), and obtains a sum of (1). The output is NOT A PERFECT NUMBER followed by 1. No special primality test is needed because the divisor-pair procedure handles primes naturally.

For the perfect square (n=36), the loop eventually reaches (d=6), where (q=36/6=6). The algorithm adds (6) once through the first condition and refuses to add it again because q != d is false. The other pairs contribute (1,36), (2,18), (3,12), and (4,9), with (36) itself excluded. The resulting sum is (55), so the output is NOT A PERFECT NUMBER followed by 55.

For the perfect number (n=6), the pairs are (1,6) and (2,3). The algorithm adds (1), rejects (6), then adds (2) and (3), producing (6). The equality test succeeds, giving PERFECT NUMBER followed by 6. This confirms that the same divisor-pair machinery works for a genuine perfect number without requiring any hard-coded list of known perfect numbers.