src/com/michaelho/DivideAndConquer/DC1.java
/**
     * Using divide and conquer method, a faster approach calculates in less time complexity.
     * See https://www.geeksforgeeks.org/karatsuba-algorithm-for-fast-multiplication-using-divide-and-conquer-algorithm/
     * for the formula.
     *
     * @param binaryX The first number as binary string.
     * @param binaryY The second number as binary string.
     *
     * @return The calculation result in integer number.
     * */
Using divide and conquer method, a faster approach calculates in less time complexity.

@param binaryX The first number as binary string.
@param binaryY The second number as binary string.

@return The calculation result in integer number.
Using divide and conquer method a faster approach calculates in less time complexity . @param binaryX The first number as binary string . @param binaryY The second number as binary string . @return The calculation result in integer number .
int calculateBinaryByFastApproach(String binaryX, String binaryY) {
        String extra = "";
        for (int i = 0; i < Math.abs(binaryY.length() - binaryX.length()); i++) {
            extra += "0";
        }
        if (binaryX.length() < binaryY.length()) {
            binaryX = extra + binaryX;
        } else if (binaryX.length() > binaryY.length()) {
            binaryY = extra + binaryY;
        }
        int n = binaryX.length();
        if (n == 0) return 0;
        if (n == 1) return Integer.valueOf(binaryX)*Integer.valueOf(binaryY);
        int firstHalf = n/2;   
        int secondHalf = (n-firstHalf); 
        String xL = binaryX.substring(0, firstHalf);
        String xR = binaryX.substring(firstHalf);
        String yL = binaryY.substring(0, firstHalf);
        String yR = binaryY.substring(firstHalf);
        int A = calculateBinaryByFastApproach(xL, yL);
        int B = calculateBinaryByFastApproach(xR, yR);
        int C = calculateBinaryByFastApproach(addBinary(xL, xR), addBinary(yL, yR));
        return A*(1<<(secondHalf*2)) + (C - A - B)*(1<<(secondHalf)) + B;
    }
int calculateBinaryByFastApproach ( String binaryX , String binaryY ) { String extra = "" ; for ( int i = 0 ; i < Math . abs ( binaryY . length ( ) - binaryX . length ( ) ) ; i ++ ) { extra += "0" ; } if ( binaryX . length ( ) < binaryY . length ( ) ) { binaryX = extra + binaryX ; } else if ( binaryX . length ( ) > binaryY . length ( ) ) { binaryY = extra + binaryY ; } int n = binaryX . length ( ) ; if ( n == 0 ) return 0 ; if ( n == 1 ) return Integer . valueOf ( binaryX ) * Integer . valueOf ( binaryY ) ; int firstHalf = n / 2 ; int secondHalf = ( n - firstHalf ) ; String xL = binaryX . substring ( 0 , firstHalf ) ; String xR = binaryX . substring ( firstHalf ) ; String yL = binaryY . substring ( 0 , firstHalf ) ; String yR = binaryY . substring ( firstHalf ) ; int A = calculateBinaryByFastApproach ( xL , yL ) ; int B = calculateBinaryByFastApproach ( xR , yR ) ; int C = calculateBinaryByFastApproach ( addBinary ( xL , xR ) , addBinary ( yL , yR ) ) ; return A * ( 1 << ( secondHalf * 2 ) ) + ( C - A - B ) * ( 1 << ( secondHalf ) ) + B ; }
Using divide and conquer method, a faster approach calculates in less time complexity.
Using divide and conquer method a faster approach calculates in less time complexity .
// Add zeros // Base cases // First half of string, floor(n/2) // Second half of string, ceil(n/2) // Find the first half and second half of second string // Recursively calculate the three products of inputs of size n/2 // Combine the three products to get the final result.