All your solution is wrong


  • 0
    J

    if the input is 61,the leetcode expected answer is 2066242608,but my answer is 2142770112 much larger than your expected answer.
    the 2142770112 is product of [2, 3, 7, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3].
    too simple too naive, when the input is larger than 60,the problem is dramatically changed.
    this is my accepted code ,so I think the problem is partly wrong.

    public int integerBreak(int n) {
    		int m = (int) (Math.log10(Integer.MAX_VALUE) / Math.log10(3));
    		if (n < 2)
    			return 1;
    		if (n <= 7)
    			return n / 2 * (n - n / 2);
    		if (n <= 3 * m + 1) {
    			if (n % 3 == 0)
    				return (int) Math.pow(3, n / 3);
    			if (n % 3 == 1)
    				return (int) Math.pow(3, n / 3 - 1) * 4;
    			if (n % 3 == 2)
    				return (int) Math.pow(3, n / 3) * 2;
    		}
    		if (n > 3 * m + 1) {
    
    		}
    		return 0;
    	}
    

  • 0
    M

    How did you get the answer? Could you post some code?


  • 0
    .

    Agreed.
    I was myself stumped when I discovered that max product can be dramatically large.
    Take the case of n = 90.

    Break it as [ 2, 2, 2, ...... , 2, 2, 2 ] and you get a product of 35184372088832

    Break it as [ 3, 3, 3, ...... , 3, 3, 3 ] and you get a product of 205891132094649

    And expected answer is: 2124471432


  • 0
    C

    61 breaks into
    [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2]
    in my code, whose product is
    4649045868.

    My theory is this:
    For positive ints who are bigger than 4, the product always increases(except for powers of 2 and three) when the number is broken down into two n/2, since n^2 / 4 is always bigger than n when n > 4. Then we have choices of breaking numbers into [1,2,3,4]. Here, since 4 = 2*2, 4 can be dropped, and 1 is meaningless, it can be dropped do. So number should always break into sum of [2,3], and it is easy to know that it is always beneficial to prefer 3 to 2. In conclusion, break your number into 2 and 3 (if number is bigger than 3), and have at most two 2's.

    Here's my naïve code.

    def integer_break(n)
        return 1 if n == 2
        return 2 if n == 3
        raw_parts = [n]
        processed_parts = []
        while raw_parts.any?
            part = raw_parts[0]
            if part -3 > 1
                raw_parts[0] -= 3
                processed_parts << 3
            elsif part -2 > 1
                raw_parts[0] -= 2
                processed_parts << 2
            end
            if raw_parts[0] <4
                processed_parts << raw_parts.shift
            end
        end
        puts(processed_parts.to_s)
        processed_parts.reduce(1) {|x,y| x*y}
    end

  • 0
    T

    7 as a factor? How could it be larger than 3*3*1 or 2*2*3?


  • 0
    .

    @tototo I don't quite understand.. @jxyzmahuan has given the example with 7. Remember the sum has to be equal to 61 in his example.
    Although that is not the optimal solution and IMO neither is the 'expected answer'.
    If you break 61 as [ 2, 2, 3, 3, 3, ...., 3, 3 ] you get a product of 4649045868.
    Also, check the example of n = 90 in my previous comment.


  • 0
    J

    @tototo I know the factor must be 2 or 3 ,but if the test case larger than 61 then overflow. I think we must find the largest number not over flow.


  • 0
    J

    @cjeon I know the factor must be 2 or 3 ,but if the test case larger than 61 then overflow. I think we must find the largest number not over flow.


  • 0
    J

    @tototo know the factor must be 2 or 3 ,but if the test case larger than 61 then overflow. I think we must find the largest number not over flow.


  • 0
    J

    @mishrasonu1993 my code is

    public int integerBreak(int n) {
    int m = (int) (Math.log10(Integer.MAX_VALUE) / Math.log10(3));
    if (n < 2)
    return 1;
    if (n <= 7)
    return n / 2 * (n - n / 2);
    if (n <= 3 * m + 1) {
    if (n % 3 == 0)
    return (int) Math.pow(3, n / 3);
    if (n % 3 == 1)
    return (int) Math.pow(3, n / 3 - 1) * 4;
    if (n % 3 == 2)
    return (int) Math.pow(3, n / 3) * 2;
    }
    if (n > 3 * m + 1) {

    	}
    	return 0;
    }

  • 0

    This was apparently not intended and the note has just been extended to say "You may assume that n is not less than 2 and not larger than 58."


Log in to reply
 

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