Math

Start on Jan 28th 2018 

End on Feb 10th 2018

(1) Conversion To/From Integers

7. Reverse Integer (N)

    int reverse(int x) {
        long r = 0;
        while (x) {
            int remainder = x % 10;
            r = r * 10 + remainder;
            x /= 10;
        }
     
        return (r >= INT_MIN && r <= INT_MAX) ? r : 0;

    }


8.  String to Integer (atoi) (N)

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

12. Integer to Roman (N)
       Define number to char map using string array for 1,2,...9,  10,20, ...90, 100,200,...900,
       1000,2000,3000 as follows:
       string M[] = {"", "M", "MM", "MMM"};
        string C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        string X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        string I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
     
        The result Roman denotation will be:
        return M[num / 1000] + C[(num % 1000) / 100] + X[(num % 100) / 10] + I[num % 10];
    }

13  Roman to Integer (N)

 Define a map between the char and its value:

 unordered_map<char, int> map = {{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
                             {'C', 100}, {'D', 500}, {'M', 1000}};

For loop  each char to calculate the total value represented by the string. If the 

current char value is greater or equal than the next one add it to  the result. Otherwise if 

it is less than the next one, minus it from the result. Return the result after the loop.

(2) Is Certain kind of Number ? 

2.1 Is Power of N

326. Power of Three (N)
        For all integer number that is a power of three, it must only contains factor/divisor 3. If we get the maximum Power of three within integer, all the numbers that is power of three should divide it.
Therefore, we can just return the remainder of  maximum Power of three within integer (3^19 = 1162261467) by n, if it is equal 0, then  n is power of three, otherwise it is not.
i.e:  return (1162261467 / n == 0);

231 Power of Two (N)
Same idea with 326 Power of Three


50. Pow(x, n) (N)
The naive O(N) solution would TLE

So the better binary search solution is O(lgN) recursion algorithm. i.e: cut the size n by half, and recursively call Pow(x, n/2), if n is even then res = half * half, otherwise res = half * half * x.  Note don't call myPow  Instead call once and save it to a temp and use it multiple times.

Note n could be negative in which case we need to get the absolute value of n, remember to use long type to hold value of n, and then get the absolute value of the long variable, only in that way, we won't have integer overflow problem.

728 Self Dividing Numbers    (N)
For loop all the numbers within the given range and if it is a Self Dividing Numbers  (SDN) number, put it in the result array list. Finally return the array list.
In order to decide whether a given number is a SDN, for loop each digit within it and calculate the remainder for that digit, if the remainder is non-zero (or  the digit is zero) then it is not a SDN, otherwise keep check all the other digits. After checking all the digits, if they can all divide the original value, then we have a SDN number.


263 Ugly Number (N)
       keep divide 2, 3, 5 while it is divisible by 2,3,5. Eventually, if it is equal to 1 then it is an ugly number, otherwise it is not. Special case is n == 0, which is not a ugly number.


367 Valid Perfect Square (N)
(Solution 1)
O(sqrt(n)) algorithm, O(1) space
1  = 1
4  = 1 + 3
9  = 1 + 3 + 5
16 = 1 + 3 + 5 + 7
...

(Solution 2)
O(lg(n)) binary Search algorithm, O(1) space


(Solution 3)
Newton's iterative algorithm O(lgN), O(1) space
x(k+1) = (x(k) + n/x(k))/2; when k-> inf, x(k)->sqrt(n)
while (xk * xk > num) keep iterating,  when out of the loop, check whether
xk * xk == num.
(https://en.wikipedia.org/wiki/Integer_square_root#Using_only_integer_division)


441. Arranging Coins (N)
(Solution 1, O(lgN), assuming sort is O(lgN))
Concept:
1+2+3+...+x = n
-> (1+x)x/2 = n
-> x^2+x = 2n
-> x^2+x+1/4 = 2n +1/4
-> (x+1/2)^2 = 2n +1/4
-> (x+0.5) = sqrt(2n+0.25)
-> x = -0.5 + sqrt(2n+0.25)
So just return floor(sqrt(2.0*n + 0.25) - 0.5);

(Solution 2, binary search O(lgN))
Since we know (x^2+x) / 2 = n, we iterate in binary search to use (x^2+x) / 2 to approach n.
i.e:  mid = low + (high - low ) /2
if ((0.5 * mid * mid + 0.5 * mid) <= n)
         low = mid + 1;
else
         high = mid - 1

   return (low - 1)


69. Sqrt(x) (Y)
Same with 441. Arranging Coins, binary search. Except use if (mid <= n / mid) to replace if ((0.5 * mid * mid + 0.5 * mid) <= n)



319 Bulb Switcher (N)
A light will be toggled only during the round of its factors, e.g. number 6 light will be toggled at 1,2,3,6 and light 12 will be toggled at 1,2,3,4,6,12. The final state of a light is on and off only depends on if the number of its factor is odd or even. If odd, the light is on and if even the light is off. The number of one number’s factor is odd if and only if it is a perfect square!
So we will only need to loop to find all the perfect squares that are smaller than n!
Actually, the number of perfect square number within n is sqrt(n)


633 Sum of Square Numbers (Y)
For every number less than C^(1/2),  check whether b = c - a*a is a square number (367 Valid Perfect Square)


9 Palindrome Number (N)
Reverse the number and compare it with the original value (note don't use string for reverse). And if you reverse the whole number, you should use long type for the reverse value to avoid integer overflow ( like 12 3456 7890


507 Perfect Number (Y)

In this method, instead of iterating over all the integers to find the factors of $num$, we only iterate upto the $\sqrt{n}$. The reasoning behind this can be understood as follows.

Consider the given number $num$ which can have $m$ distinct factors, namely $n_1,n_2,\mathrm{.}\mathrm{.}\mathrm{.},n_m$. Now, since the number $num$ is divisible by $n_i$, it is also divisible by $n_j=num\mathrm{/}{n}_1$ i.e. $n_i\ast n_j=num$. Also, the largest number in such a pair can only be up to $\sqrt{num}$ (because $\sqrt{num}\times \sqrt{num}=num$). Thus, we can get a significant reduction in the run-time by iterating only upto $\sqrt{num}$ and considering such $n_i$'s and $n_j$'s in a single pass directly.

（3） Number Theory

279 Perfect Squares (Y)

here is the Lagrange’s Four Square theorem - Limit the result to <= 4:
https://en.wikipedia.org/wiki/Lagrange’s_four-square_theorem

Basically, it says every natural number can be expressed by the summation of at most 4 square numbers. i.e n = a^2 + b ^2 + c ^2 + d^2 ( a,b,c,d = 0,1,2,3...)

More specifically, if the number contains factor 4, we can divide it by 4 and without losing generality (since 4=2^2). After that if n is (8*m + 7) m = 0,1,2.. then it can be split into 4 numbers exactly. Otherwise, it can be either split into 2 squares or 3 three squares, we can try all the number combination until sqrt(n) to check whether it is the sum  of two squares, if so return 2. Otherwise, it must be a square of at least numbers.

DP:

V1 O(N^2) time

Base case: for (i = 0 to sqrt(n) dp[i] = 1) 

for (i = 2 to n inclusive)

    for (j = 1 to i exclusive)

       dp[i] = min(dp[i], dp[j] + dp[i-j]);




V1 O(N^(3/2)) time

Base case: for (i = 0 to sqrt(n) dp[i] = 1) 

for (i = 2 to n inclusive)

    for (j = 1 to sqrt(i) exclusive)

       dp[i] = min(dp[i], dp[i - j * j] + 1);

365  Water and Jug Problem (Y)
The desired result volume (z) must be the multiple of the Greatest Command Divisor of the two jugs volume (x, y) in order to have a feasible solution.

return (z % GCD(x, y)) == 0;
https://en.wikipedia.org/wiki/Bézout%27s_identity
https://zh.wikipedia.org/wiki/貝祖等式

(4) Calculate Summation

258.   Add Digits (N)
return num != 0 ? (num % 9 != 0 ? num % 9 : 9) : 0;

415  Add Strings     (N)
This is very similar to  linked list summation: 2 Add Two Numbers
The idea is to get the size of both string and assign them to two iterator varaibles, while either of them is greater or equal than zero. Get the current chars of both string and convert them to integers
and sum them together and record the carry. (if the variable is already less than 0, return value 0 as the value of a fake char). After the loop, add the carry bit if it is greater than zero.

67. Add Binary (N)
      Same with 415  Add Strings, except sum mod  base 2 instead of sum mod base 10 to get the result digit, and divide by base 2 instead of divide by base 10 to get the carry.

598 Range Addition II    (Y)
get the minimum of all the row numbers and the miminum of all the
  column numbers, then the product of them will be the result.
  We are actually looking for the intersection of all the regions
  with the same left top point (0, 0), these numbers in the inserction
  area have the maximum value

66. Plus One (N)
      Initialize carry to 1, and loop from the last element and add the carry value to it and get the sum. Update the digit with sum % 10, and update carry with sum / 10. After the loop, if carry is not equal to zero, then insert the carry value to the beginning of the result array.



453 Minimum Moves to Equal Array Elements   (Y)
    minimum steps = total sum of the array numbers - minVal * nums.size()
    If you think about this in the form of gird, it is exactly the area over the minimum value

let’s define sum as the sum of all the numbers, before any moves; minNum as the min number int the list; n is the length of the list;

Mathematical Proof:

After, say m moves, we get all the numbers as x , and we will get the following equation

 sum + m * (n - 1) = x * n

and actually,

  x = minNum + m

and finally, we will get

  sum - minNum * n = m

171. Excel Sheet Column Number   (N)
for (const auto & c : s)  res = res * 26 + (c - 'A' + 1);


168 Excel Sheet Column Title (Y)
remainder = (n-1) % 26
n = (n - 1) / 26
Most important to use shift left n value by minus one to simplify the algorithm

628. Maximum Product of Three Numbers (N)

The max product is always either the product of the right most three elements or the two left most elements multiply the right most element.



268. Missing Number. (N)

       (1) Calculate the total sum of the given array (either for loop or use STL accumulate interface)
       (2) the missing number = N * (N + 1) / 2 - sum. ( Where N is the size of input array)


202 Happy Number (Y)
Use a unordered_set to record the numbers have encountered so far while repeatedly calculating the sum of digits squares, if we run into a sum that already in the set, that means there is a cycle, it could not be a happy number. Otherwise keep loop until we reach 1, then we have a happy number.


645  Set Mismatch (N)
Use an extra count array to count the occur frequency for number 1-n, the one that occur twice  is the repeated number, and the one that occur zero time is the missing number.



172 Factorial Trailing Zeroes (N)
      Add all the numbers that can be divided by the power of 5 not including 0 (i.e: 5^1=5, 5^2=25,
      5^3=125, ...)


43.  Multiply Strings (Y)
Use nested for loop to calculate the multiplication of each digit from the back of both array. For each result digit, it is coming from the remainder of 10 for three parts: (1) the multiplication of the two digits from both array, the carry over from last multiplication for i*(j-1) and the existing result (the high digits) from previous i-1 loop with each j. Sum the three parts together, then sum % 10 will be the new digit, and sum / 10 will be the carry for i * j.  Remember the carry bit should be define and initialized in the outer loop before the inner loop.


264 Ugly Number II (Y)
Get the nth ugly number. Using constructive way to calculate the nth ugly number.
Define an array which has 1 number which is number 1. Use three variables i,j,k to track the index of the last min value get by multiple 2, 3 and 5. Then get the minimum value of res[i]*2, res[j]*3, res[k]*5 and push back to the vector array. Then if the back value of the vector is equal to res[i]*2, ++i. If the back value of the vector is equal to res[j]*j, ++j. if the back value of the vector is equal to res[k]*k ++k (note this is not else if, else but three consecutive if, sine we could have tie comparison).  Keep construct the ugly number until count reach value n, then return the back value of result.


313 Super Ugly Number (Y)
Same with 264 Ugly Number II, but we need to define a index array (instead of using variable i,j,k..) to contain the index for each prime number in the set.





537 Complex Number Multiplication (Y)
Nothing, but how to use stringstream in C++ to split the real part and the image part of a complex number.
 string complexNumberMultiply(string a, string b) {
        int ra, ia, rb, ib;
        char buf;
        stringstream aa(a), bb(b), res;
        aa >> ra >> buf >> ia >> buf;
        bb >> rb >> buf >> ib >> buf;
        res << ra * rb - ia * ib << '+' << ra * ib + rb * ia << 'i';
     
        return res.str();
    }


204 Count Primes (Y)
Eratosthenes Sieve for prime numbers
Time O(N*N^(1/2)) = O(N^(1.5)), Space O(N)
Mark all 1-n numbers as prime number initially. Then cross out the one divisible by 2, and then cross out the one divisible by 3, then 5, 7 (i.e. cross out all the numbers that divisible by previous prime number left), then the remaining one are the real prime numbers.

https://upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif


400. Nth Digit (Y)
Step 1: calculate how many digits the number has.
Step2: calculate the number value which contains the target digit    
Step3: Get the target digit 'n' in the number



775 Global and Local Inversions (Y)
All local inversions are global inversions.
If the number of global inversions is equal to the number of local inversions,
it means that all global inversions in permutations are local inversions.
It also means that we can not find A[i] > A[j] with i+2<=j.
In other words, max(A[i]) < A[i+2]



553 Optimal Division (Y)

Using some simple math we can find the easy solution of this problem. Consider the input in the form of [a,b,c,d], now we have to set priority of operations to maximize a/b/c/d. We know that to maximize fraction $p\mathrm{/}q$, $q$(denominator) should be minimized. So, to maximize $a\mathrm{/}b\mathrm{/}c\mathrm{/}d$ we have to first minimize b/c/d. Now our objective turns to minimize the expression b/c/d.

There are two possible combinations of this expression, b/(c/d) and (b/c)/d.

b/(c/d)        (b/c)/d = b/c/d
(b*d)/c        b/(d*c)
d/c            1/(d*c)

Obviously, $d\mathrm{/}c>1\mathrm{/}(d\ast c)$ for $d>1$.

You can see that second combination will always be less than first one for numbers greater than $1$. So, the answer will be a/(b/c/d). Similarly for expression like a/b/c/d/e/f... answer will be a/(b/c/d/e/f...).

523. Continuous Subarray Sum (Y)

There is really no need to use map, a hash set is sufficient, the required length is at least 2, so we just need to insert the mod one iteration later.

535. Encode and Decode TinyURL (Y)

Simple but not very secure solution

Use a vector<string> url to save the longUrl and decode the shortUrl to the prefix followed by the vector array size - 1. When decoding just return url[index].

413. Arithmetic Slices (Y)

we can just keep a track of the number of consecutive 3-element satisfying the common differnce criteria in a $count$ variable and just update the $sum$ directly as$count\ast (count+1)\mathrm{/}2$ whenver an element not satisfying this criteria is found. At the same time, we also need to reset the $count$ value.

462 Minimum Moves to Equal Array Elements II (Y)  

Short summary: triangle inequality

Long proof:

// The Best Meeting Point problem can be reduced to a 1-dimension pure math problem:

// Given an increasing sequence {xi=1:N}, find real number x to minimize function f(x) := Σi=1:N |x-xi|.
// Simply grouping the sum into pairs:

// f(x) = Σi=1:N/2 (| x-x(i) | + | x-x(N+1-i) |) + (N%2)*| x-x(N/2+1) |.
// Note that we don't have the last term if N is even since they are all grouped into pairs. I will explain why we need to (have to) group the sum in such a form later.

// Using triangle inequality, |x-x(i)| + |x-x(N+1-i)| >= |x(N+1-i) - x(i)| = x(N+1-i) - x(i), and the fact N%2 >= 0, so we can find a lower bound for f

// f(x) >= Σi=1:N/2 (x(N+1-i) - x(i)),
// which means if we could actually pick an x to achieve this value, we find the optimal x!

// Actually, inequality |x-x(i)| + |x-x(N+1-i)| >= |x(N+1-i) - x(i)| achieves equality if and only if x is in [x(i), x(N+1-i)]. Since {xi=1:N} is increasing, closed interval sequence { [x(i), x(N+1-i)] }i=1:N/2 is nested, and so they have non-empty common intersection [x(N/2), x(N-N/2+1)]. This is critical, and this is why we need to design the grouping like this. Now it is trivial to see that picking any value in the intersection [x(N/2), x(N-N/2+1)] will reach the minimum if N is even, and only x = x(N/2+1) can reach the minimum if N is odd (since we also have to make |x-x(N/2+1)| zero).

166 Fraction to Recurring Decimal (Y)

Well, the key to this problem is on how to identify the recurring parts. After doing some examples using pen and paper, you may find that for the decimal parts to recur, the remainders should recur. So we need to maintain the remainders we have seen. Once we see a repeated remainder, we know that we have reached the end of the recurring parts and should enclose it with a ). However, we still need to insert the ( to the correct position. So we maintain a mapping from each remainder to the position of the corresponding quotient digit of it in the recurring parts. Then we use this mapping to retrieve the starting position of the recurring parts.

592. Fraction Addition and Subtraction (Y)
(1) Use istringstream object to split the input into numerator, divisor operator and denominator
(2) Use  the fact A/B + (a/b) = (A*b + a * B) / (B * b) to calculate the summation

 string fractionAddition(string expression) {
        istringstream in(expression);
        int A = 0, B = 1, a, b;
        char divide;
        while (in >> a >> divide >> b) {
            // Note: A is the current numerator result from previous calculation
            // Note: B is the current denominitor result from previous calculation
            // Therefore A/B + (a/b) = (A*b + a * B) / (B * b)
            A = A * b + a * B;
            B *= b;
            // Note std::gcd is not available until c++17,
            // For now we can only use the buildin __gcd
            int g = abs(__gcd(A, B));
            A /= g;
            B /= g;
        }
        return to_string(A) + '/' + to_string(B);
    }

223.         Rectangle Area (Y)
 Calculate the total area, overlapping is calculated twice
 subtract the overlapping area

672. Bulb Switcher II (Y)

As before, the first 6 lights uniquely determine the rest of the lights. This is because every operation that modifies the $x$-th light also modifies the $(x+6)$-th light, so the $x$-th light is always equal to the $(x+6)$-th light.

Actually, the first 3 lights uniquely determine the rest of the sequence, as shown by the table below for performing the operations a, b, c, d:

• Light 1 = 1 + a + c + d
• Light 2 = 1 + a + b
• Light 3 = 1 + a + c
• Light 4 = 1 + a + b + d
• Light 5 = 1 + a + c
• Light 6 = 1 + a + b

So that (modulo 2):

• Light 4 = (Light 1) + (Light 2) + (Light 3)
• Light 5 = Light 3
• Light 6 = Light 2

The above justifies taking $n=min(n,3)$ without loss of generality. The rest is now casework.

Let's denote the state of lights by the tuple $(a,b,c)$. The transitions are to XOR by $(1,1,1),(0,1,0),(1,0,1),$or $(1,0,0)$.

When $m=0$, all the lights are on, and there is only one state $(1,1,1)$. The answer in this case is always 1.

When $m=1$, we could get states $(0,0,0)$, $(1,0,1)$, $(0,1,0)$, or $(0,1,1)$. The answer in this case is either $2,3,4$ for $n=1,2,3$ respectively.

When $m=2$, we can manually check that we can get 7 states: all of them except for $(0,1,1)$. The answer in this case is either $2,4,7$ for $n=1,2,3$ respectively.

When $m=3$, we can get all 8 states. The answer in this case is either $2,4,8$ for $n=1,2,3$ respectively.

593 Valid Square (N)

// My Solution 1:  validate the smaller 4 side squares are equal.

// From others, validate the 6 side squares only have two unique value (the smaller one

// for the side square, and the large one for the diagonal square)

640. Solve the Equation (Y) HARD

The idea is using two pointers to update two parameters: the coefficient of x and the total sum. On the left and right side of ‘=’, we have to use opposite signs for each numbers, so I define a sign variable, which will flip if ‘=’ is seen.

Update the coefficent when meet string char 'x'

Update total when meet '+','-' and '='

670 Maximum Swap (Y)

O(N) time and O(1) space:

Actually this problem can be easily solved by only one pass from backward. During the scan, we only need to do 2 things:

1. record the largest digit (maxdigit) and its corresponding index (maxidx);
2. if the current digit is smaller than the largest digit, this digit and the largest digit are the best candidate for max swap so far. In this case, this digit pair is recorded (leftidx and rightidx).

372   Super Pow (Y)

One knowledge: ab % k = (a%k)(b%k)%k
Since the power here is an array, we’d better handle it digit by digit.
One observation:
a^1234567 % k = (a^1234560 % k) * (a^7 % k) % k = (a^123456 % k)^10 % k * (a^7 % k) % k

Looks complicated? Let me put it other way:
Suppose f(a, b) calculates a^b % k; Then translate above formula to using f :

f(a,1234567) = f(a, 1234560) * f(a, 7) % k = f(f(a, 123456),10) * f(a,7)%k;

396 Rotate Function (N) 

calculate each F(i) and  get the maximum of them.
The rotation operation could be done by pop_back and insert at the beginning.


368. Largest Divisible Subset (Y)
Thoughts：
dp
dp array used to denote the laregest divisible subset size from 0~i (inclusive)
pre array is used to record the transition direction, used to backtracking the set
dp[i]=max{dp[i],dp[j]+1}
(1) For each dp[i], calculate the following, if any number nums[j] update to i (exclusive)
can divide nums[i] and its dp[j] value plus one is greater than the current dp[i] value
then update dp[i] = dp[j] + 1 and update the previous position so we know how to construct
the subset when backtracking later.
(2) Loop the dp array again to get the largest divisible subset size in the dp array and its index
(3) Construct the divisble subset array using the pre array
(4)  reverse the result array in step (3) and return it



423 Reconstruct Original Digits from English (Y)

The idea is:

for zero, it’s the only word has letter ‘z’,
for two, it’s the only word has letter ‘w’,
…
so we only need to count the unique letter of each word, Coz the input is always valid.

For these number that doesn't contain  unique chars like "five",  we could count the frequency of

'f' and minus the frequency of 'u', then we get the occurrence time of five. 

Note we do here based on the fact that Input is guaranteed to be valid and can be transformed to its original digits.

754 Reach a Number (Y)
    int reachNumber(int target) {
        int k = 0;
        int sum = 0;
        target = abs(target);
        while (sum < target) sum += (++k);                
        const int d = sum - target;
        // d is even, return k
        if (d % 2 == 0)
            return k;
        // d is odd and k is even, then return (k + 1) since (d + k + 1) is even
        // d is odd and k is odd, then return (k + 2), since d - (k+1) + (k+2) = d + 1 is even
        return k + 1 + (k % 2);
    }

357 Count Numbers with Unique Digits (Y)

1. When n > 10, 10^(n-1) ≤ x < 10^n MUST have MORE THAN 10 digits.
2. 
   

As the Pigeonhole principle says, there MUST be AT LEAST N - 9 repeating numbers.

All numbers should be ignored, which means ***A(n) = 0 (n > 10)***.

2. When n ≤ 10, 10^(n-1) ≤ x < 10^n (all numbers with ONLY n digits) have unique digits :

• Choose n different digits from {1,2,3,4,5,6,7,8,9,0}: P(10,n)
• Filter out the permutations started by 0: P(9,n-1)
• Get A(n) = P(10,n) - P(9,n-1) = 9 * P(9,n-1)
  
  i.e: sum += 9(P(9, 0) + P(9,1) + ... P(9,9))

343 Integer Break (Y)

Assume we break n into (n / x)  x’s, then the product will be xn/x, and we want to maximize it.

Taking its derivative gives us n * xn/x-2 * (1 - ln(x)).
The derivative is positive when 0 < x < e, and equal to 0 when x = e, then becomes negative when x > e,
which indicates that the product increases as x increases, then reaches its maximum when x = e, then starts dropping.

This reveals the fact that if n is sufficiently large and we are allowed to break n into real numbers,
the best idea is to break it into nearly all e’s.
On the other hand, if n is sufficiently large and we can only break n into integers, we should choose integers that are closer to e.
The only potential candidates are 2 and 3 since 2 < e < 3, but we will generally prefer 3 to 2. Why?

Of course, one can prove it based on the formula above, but there is a more natural way shown as follows.

6 = 2 + 2 + 2 = 3 + 3. But 2 * 2 * 2 < 3 * 3.
Therefore, if there are three 2’s in the decomposition, we can replace them by two 3’s to gain a larger product.

 Intuitive explanations:

If an optimal product contains a factor f >= 4, then you can replace it with factors 2 and f-2 without losing optimality, as 2*(f-2) = 2f-4 >= f. So you never need a factor greater than or equal to 4, meaning you only need factors 1, 2 and 3 (and 1 is of course wasteful and you’d only use it for n=2 and n=3, where it’s needed).

For the rest I agree, 3\*3 is simply better than 2\*2\*2, so you’d never use 2 more than twice.