LeetCode 2507 - Smallest Value After Replacing With Sum of Prime Factors

Difficulty: 🟡 Medium
Topics: Math, Simulation, Number Theory

Solution

Problem Understanding

The problem asks us to repeatedly replace a number n with the sum of its prime factors until it reaches the smallest value it can take. Prime factors should be counted with multiplicity, meaning that if a prime factor divides n multiple times, it is added to the sum as many times as it divides n. For example, 8 = 2 * 2 * 2 would be replaced by 2 + 2 + 2 = 6.

The input is a single integer n within the range 2 <= n <= 10^5. The output is the final integer obtained after repeatedly replacing n with the sum of its prime factors, which is guaranteed to eventually stabilize at some minimum value.

Important points include recognizing that for prime numbers, the process stops immediately because the number is already prime, and that composite numbers will reduce over time since the sum of prime factors is generally less than the number itself, except for primes.

Edge cases include when n is already prime, when n is a perfect power of a prime (like 8 or 27), and when n has multiple distinct large prime factors.

Approaches

Brute Force Approach

The brute-force approach would involve repeatedly factoring n into its prime factors, summing them, and repeating until no change occurs. Factoring each number up to 10^5 can be done in O(sqrt(n)), and in the worst case, the process might take up to O(log n) iterations. This is correct but may be inefficient for larger numbers or numbers with large prime factors, as factoring is not trivial.

Optimal Approach

The optimal approach leverages the fact that we only need to sum prime factors repeatedly until the number stops changing. We can precompute prime numbers up to 10^5 using a sieve, which allows us to factor any number efficiently by trial division with primes. This reduces the time spent on factorization compared to naive trial division up to sqrt(n) for every step. We continue replacing n with the sum of its prime factors until it becomes stable.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * sqrt(n))	O(1)	Repeated factorization using trial division
Optimal	O(n log log n + log n * sqrt(n))	O(n)	Uses sieve to precompute primes for faster factorization

Algorithm Walkthrough

Generate all prime numbers up to n using the Sieve of Eratosthenes. This allows us to factor numbers efficiently in later steps.
Initialize a loop to repeatedly replace n with the sum of its prime factors.
Factor the current n using the list of primes. For each prime, divide n repeatedly until it no longer divides evenly, summing up the prime each time.
After factoring all primes, if the remaining n is greater than 1, it is a prime factor itself and should be added to the sum.
Compare the sum with the current n. If the sum equals n, then n has stabilized and is the result. Otherwise, update n with the sum and repeat the process.
Return the stabilized n.

Why it works: The process is guaranteed to eventually reach a fixed point because the sum of prime factors is generally smaller than the original number, except for prime numbers. Since n is finite and decreases or stabilizes at each step, the loop terminates with the minimal value.

Python Solution

from typing import List

class Solution:
    def smallestValue(self, n: int) -> int:
        def sieve(limit: int) -> List[int]:
            is_prime = [True] * (limit + 1)
            is_prime[0] = is_prime[1] = False
            for i in range(2, int(limit ** 0.5) + 1):
                if is_prime[i]:
                    for j in range(i * i, limit + 1, i):
                        is_prime[j] = False
            return [i for i, val in enumerate(is_prime) if val]

        primes = sieve(n)
        
        while True:
            original = n
            sum_factors = 0
            temp = n
            for p in primes:
                if p * p > temp:
                    break
                while temp % p == 0:
                    sum_factors += p
                    temp //= p
            if temp > 1:
                sum_factors += temp
            if sum_factors == n:
                return n
            n = sum_factors

The solution begins by generating all primes up to n using a sieve. It then enters a loop where it factors the number n, summing its prime factors with multiplicity. The loop continues until n stabilizes, at which point it returns the result. The use of the sieve significantly reduces the time spent factoring numbers compared to naive methods.

Go Solution

func smallestValue(n int) int {
    sieve := func(limit int) []int {
        isPrime := make([]bool, limit+1)
        for i := 2; i <= limit; i++ {
            isPrime[i] = true
        }
        for i := 2; i*i <= limit; i++ {
            if isPrime[i] {
                for j := i * i; j <= limit; j += i {
                    isPrime[j] = false
                }
            }
        }
        primes := []int{}
        for i := 2; i <= limit; i++ {
            if isPrime[i] {
                primes = append(primes, i)
            }
        }
        return primes
    }

    primes := sieve(n)

    for {
        original := n
        sumFactors := 0
        temp := n
        for _, p := range primes {
            if p*p > temp {
                break
            }
            for temp%p == 0 {
                sumFactors += p
                temp /= p
            }
        }
        if temp > 1 {
            sumFactors += temp
        }
        if sumFactors == n {
            return n
        }
        n = sumFactors
    }
}

The Go implementation mirrors the Python logic. Slices are used for primes and integer division is handled carefully. The loop continues until n stabilizes, producing the minimal value. Go requires explicit initialization of boolean slices and appending to slices, which differs from Python's list comprehensions.

Worked Examples

Example 1: n = 15

Factor 15 → 3 * 5 → sum = 8 → n = 8
Factor 8 → 2 * 2 * 2 → sum = 6 → n = 6
Factor 6 → 2 * 3 → sum = 5 → n = 5
Factor 5 → prime, sum = 5 → stabilized

Result: 5

Example 2: n = 3

Factor 3 → prime, sum = 3 → stabilized

Result: 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log log n + log n * sqrt(n))	Sieve generation O(n log log n), each factorization O(sqrt(n)) and loop runs at most log n times
Space	O(n)	Space for sieve array and primes list

The sieve ensures that we can factor numbers efficiently, while the iterative replacement guarantees convergence. Space is dominated by the storage of primes up to n.

Test Cases

# Provided examples
assert Solution().smallestValue(15) == 5  # example 1
assert Solution().smallestValue(3) == 3   # example 2

# Edge and additional cases
assert Solution().smallestValue(8) == 2   # 8 -> 2+2+2=6 -> 2+3=5 -> 5 (check)
assert Solution().smallestValue(27) == 3  # 27=3*3*3 -> 9 -> 3*3 -> 6 -> 2*3 -> 5 -> 5
assert Solution().smallestValue(2) == 2   # smallest prime
assert Solution().smallestValue(100) == 7 # 100=2*2*5*5 -> 14 -> 2*7 -> 9 -> 3*3 -> 6 -> 2*3 -> 5 -> 5

Test	Why
15	Checks multiple iterations with distinct primes
3	Checks single prime number
8	Checks repeated prime factors
27	Checks powers of a prime
2	Checks the smallest possible prime
100	Checks composite number with multiple distinct primes

Edge Cases

The first edge case is when n is a prime number. This is important because the process should stop immediately, and the algorithm handles it by checking if the sum of factors equals n.

The second edge case is when n is a perfect power of a prime, like 8 or 27. These numbers reduce slowly through multiple steps, and the algorithm correctly sums repeated prime factors.

The third edge case is when n has multiple distinct large prime factors, like 100. Here, careful factorization is required, and the sieve ensures that primes up to n are considered efficiently without missing any factors. This