Recursive Multiply

Write a recursive function to multiply two positive integers without using the * operator (or / operator). You can use addition, subtraction, and bit shifting, but you should minimize the number of those operations.

思路

要求minimize运算的次数。
假设n = small * bigger

若small为偶，n = (small/2 * bigger) * 2
若small为奇，n = (small/2 * bigger) * 2 + bigger

解题

public int product(int a, int b) {
	if(a == 0 || b == 0) return 0;
	int small = (a < b) ? a : b;
	int bigger = (a > b) ? a : b;
	return helper(smaller, bigger);
}
public int helper(int smaller, int bigger) {
	if (smaller == 0) return 0;
	if (smaller == 1) return bigger;
	int half = helper((smaller >> 1), bigger);
	if (smaller % 2 == 0) {
		return half << 1;
	}
	return (half << 1) + bigger;
}

复杂度分析

时间log(N)

• ← Previous Post
• Next Post →