2507. Smallest Value After Replacing With Sum of Prime Factors LeetCode Solution
In this guide, you will get 2507. Smallest Value After Replacing With Sum of Prime Factors LeetCode Solution with the best time and space complexity. The solution to Smallest Value After Replacing With Sum of Prime Factors problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Smallest Value After Replacing With Sum of Prime Factors
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
Complexity Analysis
Time Complexity: O(\log n)
Space Complexity: O(1)
2507. Smallest Value After Replacing With Sum of Prime Factors LeetCode Solution in C++
class Solution {
public:
int smallestValue(int n) {
int primeSum = getPrimeSum(n);
while (n != primeSum) {
n = primeSum;
primeSum = getPrimeSum(n);
}
return n;
}
private:
int getPrimeSum(int n) {
int primeSum = 0;
for (int i = 2; i <= n; ++i)
while (n % i == 0) {
n /= i;
primeSum += i;
}
return primeSum;
}
}; /* code provided by PROGIEZ */
2507. Smallest Value After Replacing With Sum of Prime Factors LeetCode Solution in Java
class Solution {
public int smallestValue(int n) {
int primeSum = getPrimeSum(n);
while (n != primeSum) {
n = primeSum;
primeSum = getPrimeSum(n);
}
return n;
}
private int getPrimeSum(int n) {
int primeSum = 0;
for (int i = 2; i <= n; ++i)
while (n % i == 0) {
n /= i;
primeSum += i;
}
return primeSum;
}
} // code provided by PROGIEZ
2507. Smallest Value After Replacing With Sum of Prime Factors LeetCode Solution in Python
class Solution:
def smallestValue(self, n: int) -> int:
def getPrimeSum(n: int) -> int:
primeSum = 0
for i in range(2, n + 1):
while n % i == 0:
n //= i
primeSum += i
return primeSum
primeSum = getPrimeSum(n)
while n != primeSum:
n = primeSum
primeSum = getPrimeSum(n)
return n # code by PROGIEZ
