Last Updated: 23 Feb, 2021

# Recursive Multiply

Moderate

## 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
``````

## Approaches

### 01 Approach

• 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.