Smallest Value After Replacing With Sum of Prime Factors
MedPrompt
You are given a positive integer n.
Continuously replace n with the sum of its prime factors.
- Note that if a prime factor divides
nmultiple times, it should be included in the sum as many times as it dividesn.
Return the smallest value n will take on.
Example 1:
Input: n = 15
Output: 5
Explanation: Initially, n = 15.
15 = 3 * 5, so replace n with 3 + 5 = 8.
8 = 2 * 2 * 2, so replace n with 2 + 2 + 2 = 6.
6 = 2 * 3, so replace n with 2 + 3 = 5.
5 is the smallest value n will take on.Example 2:
Input: n = 3
Output: 3
Explanation: Initially, n = 3.
3 is the smallest value n will take on.
Constraints:
2 <= n <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process by repeatedly calculating the sum of prime factors and updating the number. For the factorization step, it uses a basic and inefficient trial division method where potential factors are checked up to the number itself.
Algorithm
- The main function
smallestValue(n)operates in a loop. - In each iteration, it computes the sum of prime factors of the current
nby calling a helper function,getSumOfPrimeFactors(n). - The helper function finds prime factors by trial division, iterating a potential divisor
dfrom 2 upwards. For a given numberk, this check can go up tokitself. - The loop continues to divide the number by
das long as it is divisible, addingdto a running sum. - If the divisor
dis not a factor, it is incremented. - The main loop checks if the calculated sum is equal to the current
n. If they are equal, a fixed point is reached, andnis returned. - Otherwise,
nis updated to the new sum, and the loop continues.
Walkthrough
The core of this method is a loop that continues until the number n stabilizes. A number stabilizes when it is equal to the sum of its own prime factors (e.g., a prime number or 4). The value of n is guaranteed to converge because the sum of prime factors of a composite number (other than 4) is strictly less than the number itself, leading to a decreasing sequence.
The factorization is performed naively. For a number k, we start checking for divisibility from d = 2. If k is divisible by d, we add d to our sum and divide k by d, repeating this until it's no longer divisible. Then we move to the next potential divisor d+1. This process continues until the number is reduced to 1.
class Solution { public int smallestValue(int n) { while (true) { int sumOfPrimeFactors = getSumOfPrimeFactors(n); if (sumOfPrimeFactors == n) { break; } n = sumOfPrimeFactors; } return n; } private int getSumOfPrimeFactors(int k) { if (k <= 3) { // Base cases for small primes return k; } int sum = 0; int temp_k = k; int d = 2; while (temp_k > 1) { if (temp_k % d == 0) { sum += d; temp_k /= d; } else { d++; } } return sum; }}Complexity
Time
O(K * N), where K is the number of iterations until convergence and N is the value of the number. In the worst case, factorizing a large prime N takes O(N) time. Since K is small, the complexity is dominated by the factorization of the initial input `n`.
Space
O(1) extra space.
Trade-offs
Pros
Conceptually simple and easy to implement.
Cons
Highly inefficient, especially for large prime numbers or numbers with large prime factors.
The time complexity for factorizing a single number
kcan be up toO(k), which is very slow for the given constraints.
Solutions
Solution
class Solution {public int smallestValue(int n) { while (true) { int t = n, s = 0; for (int i = 2; i <= n / i; ++i) { while (n % i == 0) { s += i; n /= i; } } if (n > 1) { s += n; } if (s == t) { return s; } n = s; } }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.