Multiplication of Digits

CONCEPTS USED:

Recursion

DIFFICULTY LEVEL:

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 according to the fundamentals of data structures in c++ :-

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 10^9+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 10^9+7.

SOLUTIONS:


#include <stdio.h>
long long mod = 1e9 + 7;

int multiOfDigits(long long n,long long mod){
  if(n <= 0)
    return 1;
  return (((n%10)%mod)*(multiOfDigits(n/10,mod)%mod))%mod;
}

int main(){
  int t;
  scanf("%d",&t);
  while(t--){
    long long n;
    scanf("%lld",&n);
    printf("%d\n",multiOfDigits(n,mod));
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;

int multiOfDigits(long long n,long long mod){
  if(n <= 0)
    return 1;
  return (((n%10)%mod)*(multiOfDigits(n/10,mod)%mod))%mod;
}

int main(){
  int t;cin>>t;
  while(t--){
    long long n;cin>>n;
    cout<<multiOfDigits(n,mod)<<"\n";
  }
  return 0;
}


import java.util.*;
import java.io.*;

public class Main {
  static long mod = 1000000000 + 7;
  static long multiOfDigits(long n,long mod){
    if(n <= 0)
      return 1;
    return (((n%10)%mod)*(multiOfDigits(n/10,mod)%mod))%mod;
  }
  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while(t != 0){
      long n = sc.nextLong();
      System.out.println(multiOfDigits(n,mod));
      t--;
    }
  }
}


Previous post N Digit Sum
Next post Mike and Exam

Leave a Reply

Your email address will not be published. Required fields are marked *