Short Java solution: one digit at a time solution with invariant explanation, descriptive variable names


  • 0
    M
    Example: 123 * 45
    
    digit = (3*5)%10 AND carryFromDigit = (3*5)/10 = 1
    tenDigit = (2*5 + 3*4)%10 + carryFromDigit AND carryFromTenDigit = 2
    hundredDigit = (1*5+2*4)%10 + carryFromTenDigit AND carryFromHundredDigit = 1
    thousandDigit = (1*4)%10 + carryFromHundredDigit
    
    public class Solution {
      public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) { return "0"; }
        int lengthNum1 = num1.length(), lengthNum2 = num2.length();
        StringBuilder sb = new StringBuilder(lengthNum1+lengthNum2);
        for(int targetDigit = 1, carry = 0; targetDigit < lengthNum1+lengthNum2 || carry > 0; ++targetDigit){
          //invariants:
            // 1 <= fromNum1 <= lengthNum1
            // 1 <= fromNum2 <= lengthNum2
            // fromNum1+fromNum2-1 = targetDigit ==> fromNum2=targetDigit-fromNum1+1
          for(int fromNum1 = Math.min(targetDigit, lengthNum1), 
               fromNum2=targetDigit-fromNum1+1; 
               fromNum1 >= 1 && fromNum2 <= lengthNum2;
               --fromNum1, ++fromNum2){
            carry += (num1.charAt(lengthNum1-fromNum1)-'0')*(num2.charAt(lengthNum2-fromNum2)-'0');
          }
          sb.append(carry%10);
          carry /= 10;
        }
        return sb.reverse().toString();
      }
    }
    

Log in to reply
 

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