Problem

Submissions

Hints & solutions

Discuss

Recursive Multiply

Moderate

0/80

Average time to solve is 20m

Contributed by

8 upvotes

Asked in companies

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.

Detailed explanation ( Input/output format, Notes, Images )

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 :

Sample Output 2 :

5 
12
1

Hint 1

Hint 2

Hint 3

Hint 4

Can you solve the problem by recursively adding the number to itself?

Approaches (4)

Approach 1

Approach 2

Approach 3

Approach 4

Recursion

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.

Time Complexity

O(Min(M, N)), where ‘M’ and ‘N’ are the two given positive integers.

In the worst case, we perform Min(M, N) addition operations. Assuming that each operation takes O(1) time, the overall time complexity is O(Min(M, N)).

Space Complexity

O(Min(M, N)), where ‘M’ and ‘N’ are the two given positive integers.

Extra space is required for the recursion stack. As we perform Min(M, N) addition operations, the maximum depth of the recursion stack is O(Min(M, N)). Hence, the overall space complexity is O(Min(M, N)).

(75% EXP penalty)

(100% EXP penalty)

Recursive Multiply

Console