Scale Engineer

Smallest Value After Replacing With Sum of Prime Factors

Med
#2287Time: 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.
Patterns
MathNumber Theory

Prompt

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

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 n by calling a helper function, getSumOfPrimeFactors(n).
  • The helper function finds prime factors by trial division, iterating a potential divisor d from 2 upwards. For a given number k, this check can go up to k itself.
  • The loop continues to divide the number by d as long as it is divisible, adding d to a running sum.
  • If the divisor d is 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, and n is returned.
  • Otherwise, n is 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 k can be up to O(k), which is very slow for the given constraints.

Solutions

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.

← Previous

Previous problem

Next →

Next problem