  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Multiplication of Digits

Last Updated on March 30, 2022 by Ria Pathak Recursion

Easy

### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given an integer `N`, recursively find the multiplication of digits of `N` modulus with `10^9+7`.

See original problem statement here

#### For Example:

``````Input : N = 125

Output : 10

Explanation : 1 * 2 * 5 = 10 (Multiplication of all digits of 125)``````

### SOLVING APPROACH:

The idea is quite simple :-

Recursively keep multiplying `N / 10` with `N % 10` until the value of `N` becomes equal to `0`.

### ALGORITHM:

``````multiply (N)
if (N is less than equal to 0)
return 1
else
return (N % 10) * multiply (N/10)``````

Why is it required to modulo with 109+7 ?

As the digits are multiplied, the result may exceed even the maximum limit of `long long int` data type and overflow may occur giving unexpected results, so to keep our result in the valid range of our data types, we modulo result with 109+7.

### SOLUTIONS:

```#include <bits/stdc++.h>
using namespace std;

void solve(string s,char a,char b,int n){
if(n > 0){
solve(s+ a,a,b,n-1);
solve(s+ b,a,b,n-1);
}
else{                         //If string is not empty check if the last char was b or not
if(s[s.size()-1]==b){       // If it is b then go solving with a else solve with both
solve(s + a,a,b,n-1);
}
else{
solve(s + a,a,b,n-1);
solve(s + b,a,b,n-1);
}
}
}
else if(n == 0)
cout<<s<<"\n";
}
int main(){
int t;cin>>t;
while(t--){
char a,b;cin>>a>>b;
int n;cin>>n;
string s = "";
solve(s,a,b,n);
}
return 0;
}
```
```
#include <bits/stdc++.h>
using namespace std;

void solve(string s,char a,char b,int n){
if(n > 0){
solve(s+ a,a,b,n-1);
solve(s+ b,a,b,n-1);
}
else{                         //If string is not empty check if the last char was b or not
if(s[s.size()-1]==b){       // If it is b then go solving with a else solve with both
solve(s + a,a,b,n-1);
}
else{
solve(s + a,a,b,n-1);
solve(s + b,a,b,n-1);
}
}
}
else if(n == 0)
cout<<s<<"\n";
}
int main(){
int t;cin>>t;
while(t--){
char a,b;cin>>a>>b;
int n;cin>>n;
string s = "";
solve(s,a,b,n);
}
return 0;
}
```
```
import java.util.*;
import java.io.*;

public class Main {
static void combine(String s,char a,char b,int n){
if(n > 0){
combine(s+ a,a,b,n-1);
combine(s+ b,a,b,n-1);
}
else{                   //If string is not empty check if the last char was b or not
if(s.charAt(s.length()-1)==b){       // If it is b then go solving with a else solve with both
combine(s + a,a,b,n-1);
}
else{
combine(s + a,a,b,n-1);
combine(s + b,a,b,n-1);
}
}
}
else if(n == 0)
System.out.println(s);
}
public static void main(String args[]) throws IOException {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t!=0){
char a = sc.next().charAt(0);
char b = sc.next().charAt(0);
int n = sc.nextInt();
String s = "";
combine(s,a,b,n);
t--;
}
}
}
```
```def solve(s, a, b, n):
if(n > 0):

if(s == ""):

solve(s + a, a, b, n-1)
solve(s + b, a, b, n-1)

else:

if(s[len(s)-1] == b):

solve(s + a, a, b, n-1)

else:

solve(s + a, a, b, n-1)
solve(s + b, a, b, n-1)

elif(n == 0):
print(s)

for _ in range(int(input())):

a, b, n = input().split()
n = int(n)
s = ""

solve(s, a, b, n)

```

[forminator_quiz id="703"]

This article tried to discuss the concept of Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on Recursion you can check out MYCODE | Competitive Programming.