Multiply two integers without using multiplication, division and bitwise operators, and no loops | GeeksforGeeks

By making use of recursion, we can multiply two integers with the given constraints.
To multiply x and y, recursively add x y times.

int multiply(int x, int y)

{

   /* 0  multiplied with anything gives 0 */

   if(y == 0)

     return 0;

   /* Add x one by one */

   if(y > 0 )

     return (x + multiply(x, y-1));

  

  /* the case where y is negative */

   if(y < 0 )

     return -multiply(x, -y);

}




Our minProduct function just recurses straight downwards,with increasingly small numbers
each time.It will never repeat the same call, so there 's no need to cache any information.




This algorithm will run in O( log s) time, wheres is the smaller of the two numbers.

int minProduct(int a, int b) {
        int bigger = a< b ? b : a;
        int smaller = a< b ? a : b;
        return minProductHelper(smaller, bigger);
}

int minProductHelper(int smaller, int bigger) {
        if (smaller == 0) return 0;
        else if (smaller == 1) return bigger;

        int s =smaller >> 1; // Divide by 2
        int halfProd = minProductHelper(s, bigger);

        if (smaller% 2 == 0) {
                return halfProd + halfProd;
        } else {
                return halfProd + halfProd + bigger;
        }
}
X. Avoid duplicated work:
int minProduct(int a, int b) {
        int bigger = a< b ? b : a;
        int smaller = a< b ? a : b;

        int memo[]= new int[smaller + 1];
        return minProduct(smaller, bigger, memo);
}

int minProduct(int smaller, int bigger, int[] memo) {
        if (smaller == 0) {
                return 0;
        } else if (smaller == 1) {
                return bigger;
        } else if (memo[smaller] > 0) {
                return memo[smaller];
        }

        /* Compute half. If uneven, compute other half. If even, double it. */
        int s =smaller >> 1; // Divide by 2
        int sidel =m inProduct(s, bigger, memo); // Compute half
        int side2 = sidel;
        if (smaller% 2 == 1) {
                side2 = minProduct(smaller - s, bigger, memo);
        }

        /* Sum and cache.*/
        memo[smaller] = sidel + side2;
        return memo[smaller];
}
X.
int minProduct(int a, int b) {
        int bigger = a < b ? b : a;
        int smaller = a< b ? a : b;
        return minProductHe lper(smaller, bigger);
}

int minProductHelper(int smaller, int bigger) {
        if (smaller == 0) { // 0 x bigger = 0
                return 0;
        } else if (smaller == 1) { // 1 x bigger bigger
                return bigger;
        }

        /* Compute half. If uneven, compute other half. If even, double it. */
        int s =smaller >> 1; // Divide by 2
        int sidel = minProduct(s, bigger);
        int side2 = sidel;
        if (smaller% 2 == 1) {
                side2 = minProductHelper(smaller - s, bigger);
        }

        return sidel + side2;
}
Read full article from Multiply two integers without using multiplication, division and bitwise operators, and no loops | GeeksforGeeks