Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Last Updated: 23 Feb, 2021

Recursive Multiply

Asked in companies
Paytm (One97 Communications Limited)AppleFacebook

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


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.