0

Recursive Multiply

Difficulty: MEDIUM
Contributed By
Vishal Modani
Avg. time to solve
20 min
Success Rate
80%

Problem Statement

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
Sample Input 1 :
2
5 10
3 9   
Sample Output 1 :
50
27
Explanation of sample input 1 :
For the first test case we have, M = 5 and N = 10. Therefore our result is M*N = 5*10 = 50.

For the second test case we have, we have M = 3 and N = 9. Therefore our result is M*N = 3*9 = 27.
Sample Input 2 :
3
1 5
3 4
1 1
Sample Output 2 :
5 
12
1
Reset Code
Full screen
copy-code
Console