Java 6ms solution


  • 3
    J

    I've been playing with this for a couple days, and it occurred to me - why not just normalize the char array to be zero-based (char)0, (char)1, ... values do all the iterating, and then convert back to char-based (char)'0' + 0, (char)'0' + 1, ... at the end. ...and then skip zeros in the "bottom" number to save on iterations.

    Yeah, I know there's a faster Java solution further down, but it felt pretty good to beat >96% with this...

        public class Solution {
        public String multiply(String num1, String num2) {
            char[] n1 = toI(num1.toCharArray());
            char[] n2 = toI(num2.toCharArray());
            char[] prod = new char[n1.length+n2.length];
            int carry = 0;
            int xp = 1;
            
            Arrays.fill(prod, (char)0);
            for ( int x1=n1.length-1; x1>=0; x1-- ) {
                if ( n1[x1] > 0 ) {
                    for ( int x2=n2.length-1; x2>=0; x2-- ) {
                        xp = x1 + x2 + 1;
                        int val = (int)prod[xp];
                        val = val + carry + (n1[x1] * n2[x2]);
                        prod[xp] = (char)(val % 10);
                        carry = val / 10;
                    }
                
                    if ( carry != 0 ) {
                        prod[xp-1] = (char)carry;
                        carry = 0;
                    }
                }
            }
            
            String product = String.valueOf(toC(prod));
            while ( product.charAt(0) == '0' && product.length() > 1 ) {
                product = product.substring(1);
            }
            
            return product;
        }
        
        char[] toI(char[] num) {
            for ( int n=0; n<num.length; n++ ) {
                num[n] -= '0';
            }
            
            return num;
        }
            
        char[] toC(char[] num) {
            for ( int n=0; n<num.length; n++ ) {
                num[n] += '0';
            }
            
            return num;
        }
    }

Log in to reply
 

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