Recursive Multiply

Posted: 23 Feb, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given two positive integers. Your task is to multiply the two numbers using recursion by performing a minimum number of operations. Note that you can use addition, subtraction, and/ or bit shifting, but you cannot use the multiplication or division operation.

Input Format :
The very first line of input contains an integer ‘T’ denoting the number of test cases. 

The first and the only line of every test case contains two space-separated positive integers ‘M’ and ‘N’.
Output Format :
For each test case, print the result obtained after multiplying these two numbers.
Note :
The result can be very large. So, print the answer modulo 1000000007.

You do not need to print anything, it has already been taken care of. Just return the result. 
Constraints :
1 <= T <= 10
1 <= M, N <= 10^8

Time Limit: 1 sec
Approach 1
  • Multiplication of a number is nothing but repeated addition.
  • So, a brute force approach could be to recursively add the bigger of the two numbers (M and N) to itself until we obtain the required product.
  • Let’s assume that M >= N. Then according to this approach, we recursively add ‘M’ to itself, ‘N’ times.
Try Problem