Concise 3ms Java solution


  • 0
    S

    The multiplication result will have at most num1.length() + num2.length() digits. So we start by allocating a char array of this length. The advantage of using a char array is that it can be easily (and efficiently) turned into a String by invoking the appropriate constructor.

    To compute the final result, we need to

    • multiply num1 with each digit in num2, going from the least significant to the most significant digit
    • at each iteration i starting from 0 multiply the intermediate result by 10^i
    • sum up all the intermediate results

    In the solution below we compute a running sum, adding each intermediate result to the sum as it is computed. We accumulate the sum at each position, only taking care of carries at the end so that it has to be done just once with a linear scan. The multiplication by 10^i at each iteration is achieved by decrementing startpos at each iteration.

    public String multiply(String num1, String num2) {
      char[] arr = new char[num1.length() + num2.length()];
      char[] num2c = new char[num2.length()];
    
      // Copy num2 into an auxiliary array to avoid repeated subtraction of '0'
      num2.getChars(0, num2.length(), num2c, 0);
      for (int i = 0; i < num2c.length; i++) {
        num2c[i] -= '0';
      }
    
      for (int i = num1.length() - 1, startpos = arr.length - 1; i >= 0; i--, startpos--) {
        int digit = num1.charAt(i) - '0';
        for (int j = num2c.length - 1, pos = startpos; j >= 0; j--, pos--) {
          arr[pos] += num2c[j] * digit;
        }
      }
    
      // Take care of carrys
      for (int i = arr.length - 1; i > 0; i--) {
        arr[i - 1] += arr[i] / 10;
        arr[i] = (char)(arr[i] % 10 + '0');
      }
      arr[0] += '0';
    
      // Strip leading zeros
      int leadingZeros = -1;
      while (arr[++leadingZeros] == '0' && leadingZeros < arr.length - 1);
    
      return new String(arr, leadingZeros, arr.length - leadingZeros);
    }
    

Log in to reply
 

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