Skip to main content
Talentd

Smallest Value After Replacing With Sum of Prime Factors - Solution & Explanation

MediumMathSimulationNumber Theory13 min read
Practice this problem

Problem Statement

You are given a positive integer n.

Continuously replace n with the sum of its prime factors.

  • Note that if a prime factor divides 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 <= 105

Approach Overview

Problem 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.

Approach 1: Iterative Prime Factor Sum Replacement

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.

Code

PythonJavaCC++C#JavaScript

Python

Java

C

C++

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Recursive Prime Factor Sum Replacement

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.

Code

PythonJavaCC++C#JavaScript

Python

Java

C

C++

C#

JavaScript

Complexity

Time Complexity: O(sqrt(n) log(n)), as explained previously.
Space Complexity: O(log n), because of the recursion stack.

Try this approach in the editor →

Approach 3: Brute Force Simulation

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}).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(log n), due to recursion and storage of factors.

Recursive Prime Factor Sum Replacement

Time Complexity: O(sqrt(n) log(n)), as explained previously.
Space Complexity: O(log n), because of the recursion stack.

Brute Force Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Prime Factor Sum ReplacementO(k * sqrt(n))O(1)Best general solution; minimal memory usage and clear control flow
Recursive Prime Factor Sum ReplacementO(k * sqrt(n))O(log n)Useful for demonstrating recursive problem modeling or practicing recursion

Video Solution

2507. Smallest Value After Replacing With Sum of Prime Factors | Weekly Contest 324 | LeetCode 2507 • Bro Coders • 1,144 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Smallest Value After Replacing With Sum of Prime Factors easy or hard?
The problem is rated Medium because it combines simulation with number theory. The main challenge is implementing correct prime factorization and recognizing that the process should continue until the value stabilizes.
Smallest Value After Replacing With Sum of Prime Factors Python/Java solution
Implement a helper function that calculates the sum of prime factors using trial division from 2 to sqrt(n). In a loop, replace the current number with this sum and stop when the value no longer changes. The same logic works across Python, Java, C++, and other languages.
How to solve Smallest Value After Replacing With Sum of Prime Factors in O(n)?
The standard solution does not run in O(n); it relies on prime factorization. Using trial division, each factorization takes O(sqrt(n)) time. You repeatedly compute the sum of prime factors and update the number until the result no longer changes.
What is the best approach for Smallest Value After Replacing With Sum of Prime Factors?
The iterative prime factor sum replacement approach is the most practical. Compute the sum of prime factors using trial division up to sqrt(n), replace the number, and repeat until the value stops changing. It runs in O(k * sqrt(n)) time where k is the number of iterations until stabilization, and uses O(1) extra space.
Is Smallest Value After Replacing With Sum of Prime Factors asked at Google/Amazon/Meta?
Problems involving prime factorization and repeated transformations appear in interviews at companies like Amazon, Google, and other large tech firms. The question tests number theory fundamentals, simulation, and the ability to implement efficient factorization logic.
What data structure is used in Smallest Value After Replacing With Sum of Prime Factors?
No complex data structure is required. The solution mainly uses arithmetic operations and loops to perform prime factorization. A few integer variables track the current value and the running sum of factors.
What is the time complexity of Smallest Value After Replacing With Sum of Prime Factors?
Each step requires prime factorization, which takes O(sqrt(n)) time using trial division. The replacement process repeats only a few times because the number typically decreases quickly. Overall complexity is O(k * sqrt(n)), where k is the number of iterations until the value stabilizes.

Ready to solve this problem?

Practice Smallest Value After Replacing With Sum of Prime Factors with our built-in code editor and test cases.

Practice on FleetCode
Previous

2 Keys Keyboard

Next

Count Ways to Make Array With Product