Last Updated on March 30, 2022 by Ria Pathak
CONCEPTS USED:
Recursion
DIFFICULTY LEVEL:
Easy
PROBLEM STATEMENT(SIMPLIFIED):
Given an integer
N, recursively find the multiplication of digits ofNmodulus with10^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 / 10withN % 10until the value ofNbecomes equal to0.
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 intdata 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){
if(s == ""){ //If string is empty start with any character
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){
if(s == ""){ //If string is empty start with any character
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){
if(s == ""){ //If string is empty start with any character
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.