Smallest Value After Replacing With Sum of Prime Factors solution and explanation
9 more videos on this problem
2507. Smallest Value After Replacing With Sum of Prime Factors | Weekly Contest 324 | LeetCode 2507Bro Coders · 6:15 · 1K views
LEETCODE WEEKLY CONTEST 324 - Smallest Value After Replacing With Sum of Prime FactorsJoyjit Codes · 4:42 · 818 views
Smallest Value After Replacing With Sum of Prime Factors | 2507 LeetCode|Leetcode Weekly Contest 324CodeWithSunny · 5:21 · 551 views
Leetcode Weekly contest 324 - Medium - Smallest Value After Replacing With Sum of Prime FactorsPrakhar Agrawal · 9:47 · 442 views
2507. Smallest Value After Replacing With Sum of Prime Factors (Leetcode Medium)Programming Live with Larry · 10:32 · 316 views
Leetcode 2507 Smallest Value After Replacing With Sum of Prime Factors (Java) - Leetcode Contest 324TheAnalyticGuy · 6:16 · 196 views
smallest value after replacing with sum of prime factors | Leetcode | Approach + Solutioncodecom · 7:41 · 89 views
Leetcode 2507. Smallest Value After Replacing With Sum of Prime FactorsLetsCode · 6:57 · 75 views
leetcode 2507. Smallest Value After Replacing With Sum of Prime Factors - prime factorizationCode-Yao · 10:52 · 73 views
Leetcode 6266 || Smallest Value After Replacing With Sum of Prime Factors || Leetcode Contest MediumCoding Techniques with Komal | Newton School · 10:09 · 65 views
The problem
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
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.
def sum_of_prime_factors(n):
def prime_factors(n):
factors = []
d = 2
while d * d <= n:
while (n % d) == 0:
factors.append(d)
n //= d
d += 1
if n > 1:
factors.append(n)
return factors
current = n
while True:
pf_sum = sum(prime_factors(current))
if pf_sum == current:
break
current = pf_sum
return current
# Example usage
print(sum_of_prime_factors(15)) # Output: 5import java.util.ArrayList;
import java.util.List;
public class Main {
public static int smallestValue(int n) {
int current = n;
while (true) {
int pfSum = sumOfPrimeFactors(current);
if (pfSum == current) {
break;
}
current = pfSum;
}
return current;
}
private static int sumOfPrimeFactors(int n) {
int sum = 0;
for (int d = 2; d * d <= n; d++) {
while (n % d == 0) {
sum += d;
n /= d;
}
}
if (n > 1) {
sum += n;
}
return sum;
}
public static void main(String[] args) {
System.out.println(smallestValue(15)); // Output: 5
}
}#include <iostream>
using namespace std;
int sumOfPrimeFactors(int n) {
int sum = 0;
for (int d = 2; d * d <= n; d++) {
while (n % d == 0) {
sum += d;
n /= d;
}
}
if (n > 1) {
sum += n;
}
return sum;
}
int smallestValue(int n) {
int current = n;
int pfSum;
do {
pfSum = sumOfPrimeFactors(current);
if (pfSum == current) {
break;
}
current = pfSum;
} while (true);
return current;
}
int main() {
cout << smallestValue(15) << endl; // Output: 5
return 0;
}function sumOfPrimeFactors(n) {
let sum = 0;
for (let d = 2; d * d <= n; d++) {
while (n % d === 0) {
sum += d;
n /= d;
}
}
if (n > 1) {
sum += n;
}
return sum;
}
function smallestValue(n) {
let current = n;
while (true) {
let pfSum = sumOfPrimeFactors(current);
if (pfSum === current) {
break;
}
current = pfSum;
}
return current;
}
console.log(smallestValue(15)); // Output: 5#include <stdio.h>
int sumOfPrimeFactors(int n) {
int sum = 0;
for (int d = 2; d * d <= n; d++) {
while (n % d == 0) {
sum += d;
n /= d;
}
}
if (n > 1) {
sum += n;
}
return sum;
}
int smallestValue(int n) {
int current = n;
int pfSum;
do {
pfSum = sumOfPrimeFactors(current);
if (pfSum == current) {
break;
}
current = pfSum;
} while (1);
return current;
}
int main() {
printf("%d\n", smallestValue(15)); // Output: 5
return 0;
}using System;
class Program {
static int SumOfPrimeFactors(int n) {
int sum = 0;
for (int d = 2; d * d <= n; d++) {
while (n % d == 0) {
sum += d;
n /= d;
}
}
if (n > 1) {
sum += n;
}
return sum;
}
static int SmallestValue(int n) {
int current = n;
while (true) {
int pfSum = SumOfPrimeFactors(current);
if (pfSum == current) {
break;
}
current = pfSum;
}
return current;
}
static void Main() {
Console.WriteLine(SmallestValue(15)); // Output: 5
}
}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.
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.
def sum_of_prime_factors_recursive(n):
def prime_factors(n):
factors = []
d = 2
while d * d <= n:
while n % d == 0:
factors.append(d)
n //= d
d += 1
if n > 1:
factors.append(n)
return factors
def recursive_helper(n):
pf_sum = sum(prime_factors(n))
if pf_sum == n:
return pf_sum
else:
return recursive_helper(pf_sum)
return recursive_helper(n)
# Example usage
print(sum_of_prime_factors_recursive(15)) # Output: 5public class MainRecursive {
public static int smallestValue(int n) {
return recursiveSum(n);
}
private static int recursiveSum(int n) {
int pfSum = sumOfPrimeFactors(n);
if (pfSum == n) {
return n;
}
return recursiveSum(pfSum);
}
private static int sumOfPrimeFactors(int n) {
int sum = 0;
for (int d = 2; d * d <= n; d++) {
while (n % d == 0) {
sum += d;
n /= d;
}
}
if (n > 1) {
sum += n;
}
return sum;
}
public static void main(String[] args) {
System.out.println(smallestValue(15)); // Output: 5
}
}#include <iostream>
using namespace std;
int sumOfPrimeFactors(int n) {
int sum = 0;
for (int d = 2; d * d <= n; d++) {
while (n % d == 0) {
sum += d;
n /= d;
}
}
if (n > 1) {
sum += n;
}
return sum;
}
int recursiveSum(int n) {
int pfSum = sumOfPrimeFactors(n);
if (pfSum == n) {
return n;
}
return recursiveSum(pfSum);
}
int main() {
cout << recursiveSum(15) << endl; // Output: 5
return 0;
}function sumOfPrimeFactors(n) {
let sum = 0;
for (let d = 2; d * d <= n; d++) {
while (n % d === 0) {
sum += d;
n /= d;
}
}
if (n > 1) {
sum += n;
}
return sum;
}
function recursiveSum(n) {
let pfSum = sumOfPrimeFactors(n);
if (pfSum === n) {
return n;
}
return recursiveSum(pfSum);
}
console.log(recursiveSum(15)); // Output: 5#include <stdio.h>
int sumOfPrimeFactors(int n) {
int sum = 0;
for (int d = 2; d * d <= n; d++) {
while (n % d == 0) {
sum += d;
n /= d;
}
}
if (n > 1) {
sum += n;
}
return sum;
}
int recursiveSum(int n) {
int pfSum = sumOfPrimeFactors(n);
if (pfSum == n) {
return n;
}
return recursiveSum(pfSum);
}
int main() {
printf("%d\n", recursiveSum(15)); // Output: 5
return 0;
}using System;
class Program {
static int SumOfPrimeFactors(int n) {
int sum = 0;
for (int d = 2; d * d <= n; d++) {
while (n % d == 0) {
sum += d;
n /= d;
}
}
if (n > 1) {
sum += n;
}
return sum;
}
static int RecursiveSum(int n) {
int pfSum = SumOfPrimeFactors(n);
if (pfSum == n) {
return n;
}
return RecursiveSum(pfSum);
}
static void Main() {
Console.WriteLine(RecursiveSum(15)); // Output: 5
}
}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.
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}).
func smallestValue(n int) int {
for {
t, s := n, 0
for i := 2; i <= n/i; i++ {
for n%i == 0 {
s += i
n /= i
}
}
if n > 1 {
s += n
}
if s == t {
return s
}
n = s
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
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.