Largest N digit number divisible by given three numbers
Given four integers x, y, z, and n, the task is to find the largest n digit number which is divisible by x, y, and z.
Examples:
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
Approach:
- Find the largest n digit number i.e. pow(10, n) – 1 and store it in a variable largestN.
- Find LCM of the given three numbers x, y and z say LCM.
- Calculate the remainder when largestN is divided by LCM i.e. largestN % LCM and store it in a variable remainder.
- Subtract remainder from largestN. If the result is still an n digit number then print the result.
- Else print Not possible.
Below is the implementation of the above approach:
C++
// 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
// 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
# 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#
// 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 // 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 |
Javascript
<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> |
Output:
96
Time Complexity: O(log(min(x, y,z ))) + O(log(n)) as we are doing lcm of x,y,z we need log(min(x,y,z)) time complexity for that + log(n) for doing pow(10,n-1) so overall time complexity will be O(log(min(x, y,z ))) + O(log(n))
Auxiliary Space: O(log(min(x, y, z))) + O(log(n)) as we are doing lcm of x,y,z this lcm will be done in recursively manner so recursion need extra O(log(min(x, y, z))) auxiliary stack space, and addition for doing pow(10,n-1) which is also in recursive manner which also need log(n) extra auxiliary stack space
Contact Us