Largest palindrome which is product of two n-digit numbers
Given a value n, find out the largest palindrome number which is product of two n digit numbers.
Examples :
Input : n = 2 Output : 9009 9009 is the largest number which is product of two 2-digit numbers. 9009 = 91*99. Input : n = 3 Output : 906609
Below are steps to find the required number.
- Find a lower limit on n digit numbers. For example, for n = 2, lower_limit is 10.
- Find an upper limit on n digit numbers. For example, for n = 2, upper_limit is 99.
- Consider all pairs of numbers wherever number lies in range [lower_limit, upper_limit]
Below is the implementation of above steps.
C++
// C++ problem to find out the // largest palindrome number which // is product of two n digit numbers #include <bits/stdc++.h> using namespace std; // Function to calculate largest // palindrome which is product of // two n-digits numbers int larrgestPalindrome( int n) { int upper_limit = pow (10,n) - 1; // largest number of n-1 digit. // One plus this number is lower // limit which is product of two numbers. int lower_limit = 1 + upper_limit / 10; // Initialize result int max_product = 0; for ( int i = upper_limit; i >= lower_limit; i--) { for ( int j = i; j >= lower_limit; j--) { // calculating product of // two n-digit numbers int product = i * j; if (product < max_product) break ; int number = product; int reverse = 0; // calculating reverse of // product to check whether // it is palindrome or not while (number != 0) { reverse = reverse * 10 + number % 10; number /= 10; } // update new product if exist // and if greater than previous one if (product == reverse && product > max_product) max_product = product; } } return max_product; } // Driver code int main() { int n = 2; cout << larrgestPalindrome(n); return 0; } |
Java
// Java problem to find out the // largest palindrome number // which is product of two // n digit numbers. import java.lang.Math; class GFG { // Function to calculate largest // palindrome which isproduct of // two n-digits numbers static int larrgestPalindrome( int n) { int upper_limit = ( int )Math.pow( 10 , n) - 1 ; // largest number of n-1 digit. // One plus this number // is lower limit which is // product of two numbers. int lower_limit = 1 + upper_limit / 10 ; // Initialize result int max_product = 0 ; for ( int i = upper_limit; i >= lower_limit; i--) { for ( int j = i; j >= lower_limit; j--) { // calculating product of two // n-digit numbers int product = i * j; if (product < max_product) break ; int number = product; int reverse = 0 ; // calculating reverse of product // to check whether it is // palindrome or not while (number != 0 ) { reverse = reverse * 10 + number % 10 ; number /= 10 ; } // update new product if exist and if // greater than previous one if (product == reverse && product > max_product) max_product = product; } } return max_product; } // Driver code public static void main (String[] args) { int n = 2 ; System.out.print(larrgestPalindrome(n)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python problem to find # out the largest palindrome # number which is product of # two n digit numbers. # Function to calculate largest # palindrome which is # product of two n-digits numbers def larrgestPalindrome(n): upper_limit = ( 10 * * (n)) - 1 # largest number of n-1 digit. # One plus this number # is lower limit which is # product of two numbers. lower_limit = 1 + upper_limit / / 10 max_product = 0 # Initialize result for i in range (upper_limit,lower_limit - 1 , - 1 ): for j in range (i,lower_limit - 1 , - 1 ): # calculating product of # two n-digit numbers product = i * j if (product < max_product): break number = product reverse = 0 # calculating reverse of # product to check # whether it is palindrome or not while (number ! = 0 ): reverse = reverse * 10 + number % 10 number = number / / 10 # update new product if exist and if # greater than previous one if (product = = reverse and product > max_product): max_product = product return max_product # Driver code n = 2 print (larrgestPalindrome(n)) # This code is contributed # by Anant Agarwal. |
C#
// C# problem to find out the // largest palindrome number // which is product of two // n digit numbers. using System; class GFG { // Function to calculate largest // palindrome which isproduct of // two n-digits numbers static int larrgestPalindrome( int n) { int upper_limit = ( int )Math.Pow(10, n) - 1; // largest number of n-1 digit. // One plus this number // is lower limit which is // product of two numbers. int lower_limit = 1 + upper_limit / 10; // Initialize result int max_product = 0; for ( int i = upper_limit; i >= lower_limit; i--) { for ( int j = i; j >= lower_limit; j--) { // calculating product of two // n-digit numbers int product = i * j; if (product < max_product) break ; int number = product; int reverse = 0; // calculating reverse of product // to check whether it is // palindrome or not while (number != 0) { reverse = reverse * 10 + number % 10; number /= 10; } // update new product if exist and if // greater than previous one if (product == reverse && product > max_product) max_product = product; } } return max_product; } // Driver code public static void Main () { int n = 2; Console.Write(larrgestPalindrome(n)); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP problem to find out // the largest palindrome // number which is product // of two n digit numbers // Function to calculate // largest palindrome which // is product of two n-digit numbers function larrgestPalindrome( $n ) { $upper_limit = 0; // Loop to calculate upper bound // (largest number of n-digit) for ( $i = 1; $i <= $n ; $i ++) { $upper_limit *= 10; $upper_limit += 9; } // largest number of n-1 digit // One plus this number // is lower limit which is // product of two numbers. $lower_limit = 1 + (int)( $upper_limit / 10); // Initialize result $max_product = 0; for ( $i = $upper_limit ; $i >= $lower_limit ; $i --) { for ( $j = $i ; $j >= $lower_limit ; $j --) { // calculating product of // two n-digit numbers $product = $i * $j ; if ( $product < $max_product ) break ; $number = $product ; $reverse = 0; // calculating reverse of // product to check whether // it is palindrome or not while ( $number != 0) { $reverse = $reverse * 10 + $number % 10; $number = (int)( $number / 10); } // update new product if exist // and if greater than previous one if ( $product == $reverse && $product > $max_product ) $max_product = $product ; } } return $max_product ; } // Driver code $n = 2; echo (larrgestPalindrome( $n )); // This code is contributed by Ajit. ?> |
Javascript
<script> // Javascript problem to find out the // largest palindrome number // which is product of two // n digit numbers. // Function to calculate largest // palindrome which isproduct of // two n-digits numbers function larrgestPalindrome(n) { let upper_limit = Math.pow(10, n) - 1; // largest number of n-1 digit. // One plus this number // is lower limit which is // product of two numbers. let lower_limit = 1 + parseInt(upper_limit / 10, 10); // Initialize result let max_product = 0; for (let i = upper_limit; i >= lower_limit; i--) { for (let j = i; j >= lower_limit; j--) { // calculating product of two // n-digit numbers let product = i * j; if (product < max_product) break ; let number = product; let reverse = 0; // calculating reverse of product // to check whether it is // palindrome or not while (number != 0) { reverse = reverse * 10 + number % 10; number = parseInt(number / 10, 10); } // update new product if exist and if // greater than previous one if (product == reverse && product > max_product) max_product = product; } } return max_product; } let n = 2; document.write(larrgestPalindrome(n)); </script> |
Output :
9009
Time Complexity: O(n*n*log10(product)), where n is the upper limit calculated and product is (product of two n-digit numbers)
Auxiliary Space: O(1), as no extra space is required|
The approach used in this post is simple and straightforward. Please comment if you find a better approach.
Contact Us