Mayor número de N dígitos divisible por tres números dados

Dados cuatro enteros x, y, z y n , la tarea es encontrar el número de n dígitos más grande que sea divisible por x, y y z . 

Ejemplos:

Input: x = 2, y = 3, z = 5, n = 4 
Output: 9990 
9990 is the largest 4-digit number which is divisible by 2, 3 and 5.

Input: x = 3, y = 23, z = 6, n = 2 
Output: Not possible 

Acercarse:  

• Encuentre el número de n dígitos más grande, es decir , pow(10, n) – 1 y guárdelo en una variable más grandeN .
• Encuentre LCM de los tres números dados x, y y z digamos LCM .
• Calcule el resto cuando el N más grande se divide por MCM, es decir , el N más grande % LCM y guárdelo en un resto variable .
• Resta el resto de la N más grande . Si el resultado sigue siendo un número de n dígitos, imprima el resultado.
• De lo contrario imprimir No es posible .

A continuación se muestra la implementación del enfoque anterior:
 

// C++ program to find largest n digit number
// which is divisible by x, y and z.
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the LCM of three numbers
int LCM(int x, int y, int z)
{
    int ans = ((x * y) / (__gcd(x, y)));
    return ((z * ans) / (__gcd(ans, z)));
}
 
// Function to return the largest n-digit
// number which is divisible by x, y and z
int findDivisible(int n, int x, int y, int z)
{
 
    // find the LCM
    int lcm = LCM(x, y, z);
 
    // find largest n-digit number
    int largestNDigitNum = pow(10, n) - 1;
 
    int remainder = largestNDigitNum % lcm;
 
    // If largest number is the answer
    if (remainder == 0)
        return largestNDigitNum ;
 
    // find closest smaller number
    // divisible by LCM
    largestNDigitNum -= remainder;
 
    // if result is an n-digit number
    if (largestNDigitNum >= pow(10, n - 1))
        return largestNDigitNum;
    else
        return 0;
}
 
// Driver code
int main()
{
    int n = 2, x = 3, y = 4, z = 6;
    int res = findDivisible(n, x, y, z);
 
    // if the number is found
    if (res != 0)
        cout << res;
    else
        cout << "Not possible";
 
    return 0;
}

// Java program to find largest n digit number
// which is divisible by x, y and z.
import java.math.*;
class GFG {
     
// Recursive function to return gcd of a and b
    static int gcd(int a, int b)
    {
        // Everything divides 0 
        if (a == 0)
          return b;
        if (b == 0)
          return a;
        
        // base case
        if (a == b)
            return a;
        
        // a is greater
        if (a > b)
            return gcd(a-b, b);
        return gcd(a, b-a);
    }
     
// Function to return the LCM of three numbers
static int LCM(int x, int y, int z)
{
    int ans = ((x * y) / (gcd(x, y)));
    return ((z * ans) / (gcd(ans, z)));
}
 
// Function to return the largest n-digit
// number which is divisible by x, y and z
static int findDivisible(int n, int x, int y, int z)
{
 
    // find the LCM
    int lcm = LCM(x, y, z);
 
    // find largest n-digit number
    int largestNDigitNum = (int)Math.pow(10, n) - 1;
 
    int remainder = largestNDigitNum % lcm;
 
    // If largest number is the answer
    if (remainder == 0)
        return largestNDigitNum ;
 
    // find closest smaller number
    // divisible by LCM
    largestNDigitNum -= remainder;
 
    // if result is an n-digit number
    if (largestNDigitNum >= (int)Math.pow(10, n - 1))
        return largestNDigitNum;
    else
        return 0;
}
 
// Driver code
public static void main(String args[])
{
    int n = 2, x = 3, y = 4, z = 6;
    int res = findDivisible(n, x, y, z);
 
    // if the number is found
    if (res != 0)
        System.out.println(res);
    else
        System.out.println("Not possible");
 
}
}

# Python3 program to find largest n digit
# number which is divisible by x, y and z.
 
# Recursive function to return
# gcd of a and b
def gcd(a, b):
 
    # Everything divides 0
    if (a == 0):
        return b;
    if (b == 0):
        return a;
     
    # base case
    if (a == b):
        return a;
     
    # a is greater
    if (a > b):
        return gcd(a - b, b);
    return gcd(a, b - a);
 
# Function to return the LCM
# of three numbers
def LCM(x, y, z):
    ans = ((x * y) / (gcd(x, y)));
    return ((z * ans) / (gcd(ans, z)));
 
# Function to return the largest n-digit
# number which is divisible by x, y and z
def findDivisible(n, x, y, z):
     
    # find the LCM
    lcm = LCM(x, y, z);
     
    # find largest n-digit number
    largestNDigitNum = int(pow(10, n)) - 1;
     
    remainder = largestNDigitNum % lcm;
     
    # If largest number is the answer
    if (remainder == 0):
        return largestNDigitNum ;
     
    # find closest smaller number
    # divisible by LCM
    largestNDigitNum -= remainder;
     
    # if result is an n-digit number
    if (largestNDigitNum >= int(pow(10, n - 1))):
        return largestNDigitNum;
    else:
        return 0;
 
# Driver code
n = 2; x = 3;
y = 4; z = 6;
res = int(findDivisible(n, x, y, z));
 
# if the number is found
if (res != 0):
    print(res);
else:
    print("Not possible");
 
# This code is contributed
# by mits

// C# program to find largest n
// digit number which is divisible
// by x, y and z.
using System;
 
class GFG
{
// Recursive function to return
// gcd of a and b
static int gcd(int a, int b)
{
    // Everything divides 0
    if (a == 0)
        return b;
    if (b == 0)
        return a;
     
    // base case
    if (a == b)
        return a;
     
    // a is greater
    if (a > b)
        return gcd(a - b, b);
    return gcd(a, b - a);
}
 
// Function to return the
// LCM of three numbers
static int LCM(int x, int y, int z)
{
    int ans = ((x * y) / (gcd(x, y)));
    return ((z * ans) / (gcd(ans, z)));
}
 
// Function to return the largest
// n-digit number which is divisible
// by x, y and z
static int findDivisible(int n, int x,
                         int y, int z)
{
 
    // find the LCM
    int lcm = LCM(x, y, z);
 
    // find largest n-digit number
    int largestNDigitNum = (int)Math.Pow(10, n) - 1;
 
    int remainder = largestNDigitNum % lcm;
 
    // If largest number is the answer
    if (remainder == 0)
        return largestNDigitNum ;
 
    // find closest smaller number
    // divisible by LCM
    largestNDigitNum -= remainder;
 
    // if result is an n-digit number
    if (largestNDigitNum >= (int)Math.Pow(10, n - 1))
        return largestNDigitNum;
    else
        return 0;
}
 
// Driver code
static void Main()
{
    int n = 2, x = 3, y = 4, z = 6;
    int res = findDivisible(n, x, y, z);
 
    // if the number is found
    if (res != 0)
        Console.WriteLine(res);
    else
        Console.WriteLine("Not possible");
}
}
 
// This code is contributed by ANKITRAI1

<?php
// PHP program to find largest n digit number
// which is divisible by x, y and z.
 
// Recursive function to return gcd of a and b
function gcd($a, $b)
{
    // Everything divides 0
    if ($a == 0)
        return $b;
    if ($b == 0)
        return $a;
     
    // base case
    if ($a == $b)
        return $a;
     
    // a is greater
    if ($a > $b)
        return gcd($a - $b, $b);
    return gcd($a, $b - $a);
}
 
// Function to return the LCM
// of three numbers
function LCM($x, $y, $z)
{
$ans = (($x * $y) / (gcd($x, $y)));
return (($z * $ans) / (gcd($ans, $z)));
}
 
// Function to return the largest n-digit
// number which is divisible by x, y and z
function findDivisible($n, $x, $y, $z)
{
     
    // find the LCM
    $lcm = LCM($x, $y, $z);
     
    // find largest n-digit number
    $largestNDigitNum = (int)pow(10, $n) - 1;
     
    $remainder = $largestNDigitNum % $lcm;
     
    // If largest number is the answer
    if ($remainder == 0)
        return $largestNDigitNum ;
     
    // find closest smaller number
    // divisible by LCM
    $largestNDigitNum -= $remainder;
     
    // if result is an n-digit number
    if ($largestNDigitNum >= (int)pow(10, $n - 1))
        return $largestNDigitNum;
    else
        return 0;
}
 
// Driver code
$n = 2; $x = 3; $y = 4; $z = 6;
$res = findDivisible($n, $x, $y, $z);
 
// if the number is found
if ($res != 0)
    echo $res;
else
    echo "Not possible";
 
// This code is contributed
// by Akanksha Rai

<script>
 
// Javascript program to find largest n
// digit number which is divisible
// by x, y and z.
 
// Recursive function to return
// gcd of a and b
function gcd(a, b)
{
    // Everything divides 0
    if (a == 0)
        return b;
    if (b == 0)
        return a;
     
    // base case
    if (a == b)
        return a;
     
    // a is greater
    if (a > b)
        return gcd(a - b, b);
    return gcd(a, b - a);
}
 
// Function to return the
// LCM of three numbers
function LCM(x, y, z)
{
    var ans = parseInt((x * y) / (gcd(x, y)));
    return parseInt((z * ans) / (gcd(ans, z)));
}
 
// Function to return the largest
// n-digit number which is divisible
// by x, y and z
function findDivisible(n, x, y, z)
{
 
    // find the LCM
    var lcm = LCM(x, y, z);
 
    // find largest n-digit number
    var largestNDigitNum = Math.pow(10, n) - 1;
 
    var remainder = largestNDigitNum % lcm;
 
    // If largest number is the answer
    if (remainder == 0)
        return largestNDigitNum ;
 
    // find closest smaller number
    // divisible by LCM
    largestNDigitNum -= remainder;
 
    // if result is an n-digit number
    if (largestNDigitNum >= Math.pow(10, n - 1))
        return largestNDigitNum;
    else
        return 0;
}
 
// Driver code
var n = 2, x = 3, y = 4, z = 6;
var res = findDivisible(n, x, y, z);
// if the number is found
if (res != 0)
    document.write(res);
else
    document.write("Not possible");
 
</script>

96

Complejidad del tiempo: O(log(min(x, y)))

Espacio auxiliar: O(log(min(x, y)))