Share some thought process about this problem


  • 16
    A
    If we want to break a number, breaking it into 3s turns out to be the most efficient.
    2^3 < 3^2
    4^3 < 3^4
    5^3 < 3^5
    6^3 < 3^6
    ...
    
    Therefore, intuitively, we want as many 3 as possible 
    if a number % 3 == 0, we just break it into 3s -> the product is Math.pow(3, n/3)
    
    As for numbers % 3 == 1, we don't want the 'times * 1' in the end; 
        borrowing a 3 is a natural thought. 
        if we borrow a 3, 3 can be divided into 
             case 1: 1 + 2 -> with the extra 1, we have 2*2 = 4
             case 2: (0) + 3 -> with the extra 1, we have 4
             turns out these two cases have the same results
        so, for numbers % 3 == 1 -> the result would be Math.pow(3, n/3-1)*4
    
    Then we have the numbers % 3 == 2 left
         again, we try to borrow a 3,
             case 1: 1+2 -> with the extra 2, we have 1*5 or 3*2 => 3*2 is better
             case 2: 0+3 -> with the extra 2, we have 2*3 or 5 => 2*3 is better
         and we actually just end up with not borrowing at all! 
         so we can just *2 if we have an extra 2 -> the result would be Math.pow(3, n/3)*2
    
    Then, we have a couple corner cases two deal with since so far we only looked at 
    numbers  that are larger than 3 -> luckily, we only have 2 and 3 left, 
    which are pretty easy to figure out
    
    Thus my final solution is 
    
    public class Solution {
        public int integerBreak(int n) {
            if(n <= 3) return n-1; //assuming n >= 2
            return n%3 == 0 ? (int)Math.pow(3, n/3) : n%3 == 1 ? (int)Math.pow(3, n/3-1)*4 : (int)Math.pow(3, n/3)*2;
        }
    }

  • 2
    O

    I just want to know why when should break it into 3s as more as we can ?
    is there any theorem or how to prove it?


  • 1
    I

    Okay, I will try to provide an informal proof of why we want as many 3s as possible.

    Firstly, it is easy to see why the result is n - 1 for n < 4. Therefore, we will only observe the case n >= 4.

    The most optimal way to represent 4 is 2 * 2, again easy to see. What if n > 4?

    We claim that 3 * (n - 3) > n for all n >= 5. This is indeed the case, since:

    3 * (n - 3) > n
    3n - 9 > n | -n
    2n - 9 > 0 | +9
    2n > 9 | /2
    n > 4.5 which is always true, since we assumed n >= 5.
    

    With this proof we have actually shown that for any integer bigger than 4 it is actually better to decompose it as 3 times something instead of leaving it as it is.

    Now we can recursively solve for x = n - 3. The new cases are:

     1. x == 2 - in this case we leave it as it is, which means that n % 3 == 2. 
        This is covered by (int)Math.pow(3, n/3)*2 in his solution.
     2. x == 3 - corresponds to n % 3 == 0, which is covered by (int)Math.pow(3, n/3)
     3. x == 4 - corresponds to n % 3 == 1, which is covered by 
        (int)Math.pow(3, n/3-1)*4, meaning that we multiply by 4 instead of 3 once.
     4. x >= 5 - in this case we can recursively solve for x.
    

    A natural question would be why we chose exactly 3 and not any other number? It is indeed true that for any positive integer x >= 2 we have x * (n - x) >= n for n big enough. However, it wouldn't make sense to choose x >= 5, as we have already proved that it is better to decompose it using as many 3s as possible. So the only candidates left are x = 2 and x = 4:

     1. x == 4 - We will have something like 4 * 4 * 4 ... * something. Let's take 
         only the first two factors: 4 * 4 < 3 * 3 * 2, so we can substitute all 
         of the fours with this expression, meaning that 3 is indeed the better 
         choice. For the remaining non-three factors, we can sum them up 
         and use the same recursion.
     2. x == 2 - Similarly, 2 * 2 * 2 < 3 * 3.
    

    The proof is not complete, but should be enough for you to understand the intuition.


  • 0
    B

    this is really clever. thank you for sharing


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.