You are given a positive integer n.
Continuously replace n with the sum of its prime factors.
n multiple times, it should be included in the sum as many times as it divides n.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 <= 105Problem Overview: You start with an integer n. Replace it with the sum of its prime factors (counted with multiplicity). Repeat this operation until the value no longer changes. The task is to return the smallest value reached after the process stabilizes.
Approach 1: Iterative Prime Factor Sum Replacement (O(k * sqrt(n)) time, O(1) space)
This approach directly simulates the transformation process. For a given value x, compute the sum of its prime factors using standard prime factorization: iterate from 2 to sqrt(x), repeatedly dividing whenever a factor is found. If the remaining value is greater than 1, it is also a prime factor and gets added to the sum. Replace x with this sum and continue until the new value equals the previous one. Each iteration reduces the number or keeps it the same, so the process converges quickly. This method uses only a few variables and no additional data structures, making it efficient and easy to implement using concepts from number theory and simulation.
Approach 2: Recursive Prime Factor Sum Replacement (O(k * sqrt(n)) time, O(log n) space)
The recursive version expresses the same process using function calls. Compute the prime factor sum for the current number. If the sum equals the number, return it because the value has stabilized. Otherwise, call the function again with the new sum. The recursion naturally models the repeated replacement process. The main work still happens in the prime factorization step, which iterates up to sqrt(n). The recursion depth is small because values shrink quickly, but it still uses call stack space. This approach highlights the mathematical structure of the problem and fits well when practicing recursion with math-heavy problems.
Recommended for interviews: The iterative simulation is usually preferred. It avoids recursion overhead and keeps the logic explicit: compute prime factors, update the value, repeat until stable. Showing the brute simulation first demonstrates understanding of the process, while implementing efficient prime factorization shows practical problem-solving skill expected in technical interviews.
This approach involves iteratively calculating the sum of the prime factors of a number until it stabilizes at a value that cannot be reduced further. The method utilizes a helper function to find and sum the prime factors of a given number. Once the number becomes a prime, or stays constant after transformation, the iterations stop.
This Python function defines an inner function, prime_factors(), which calculates all prime factors of a given number. The main function then repeatedly computes the sum of these factors until the number stops changing.
Time Complexity: O(sqrt(n) log(n)), where sqrt(n) comes from factorization and log(n) denotes the sum operation over iterations.
Space Complexity: O(log n), due to recursion and storage of factors.
This approach uses recursion to replace a number with the sum of its prime factors until the number becomes stable. A helper function calculates the sum of prime factors recursively.
This approach utilizes a recursive function, recursive_helper(), where we calculate the prime factors and their sum, and then call the function continuously until the number cannot be further reduced.
Time Complexity: O(sqrt(n) log(n)), as explained previously.
Space Complexity: O(log n), because of the recursion stack.
According to the problem statement, we can perform a process of prime factorization, i.e., continuously decompose a number into its prime factors until it can no longer be decomposed. During the process, add the prime factors each time they are decomposed, and perform this recursively or iteratively.
The time complexity is O(\sqrt{n}).
| Approach | Complexity |
|---|---|
| Iterative Prime Factor Sum Replacement | Time Complexity: O(sqrt(n) log(n)), where sqrt(n) comes from factorization and log(n) denotes the sum operation over iterations. |
| Recursive Prime Factor Sum Replacement | Time Complexity: O(sqrt(n) log(n)), as explained previously. |
| Brute Force Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Prime Factor Sum Replacement | O(k * sqrt(n)) | O(1) | Best general solution; minimal memory usage and clear control flow |
| Recursive Prime Factor Sum Replacement | O(k * sqrt(n)) | O(log n) | Useful for demonstrating recursive problem modeling or practicing recursion |
2507. Smallest Value After Replacing With Sum of Prime Factors | Weekly Contest 324 | LeetCode 2507 • Bro Coders • 1,087 views views
Watch 9 more video solutions →Practice Smallest Value After Replacing With Sum of Prime Factors with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor