Given a value N, find out the largest palindrome number which is the product of two N-digit numbers.
Examples:
Input: N = 2
Output: 9009
Explanation:
9009 is the largest number which is product of two 2-digit numbers 91 and 99 (9009 = 91*99)
Input: N = 3
Output: 906609
Input: N = 4
Output: 99000099
Observation: The following observation can be made for the above problem:
Let N = 2, then the product will contain 4 digits. Since the product will be a palindrome it will be of the form “abba” where a, b are digits at their respective place value.
Therefore,
For N = 2:
“abba” = 1000a + 100b + 10b + a
= 1001a + 110b
= 11.(91a + 10b)
Similarly, for N = 3:
“abccba” = 100000a + 10000b + 1000c + 100c + 10b + 1a
= 100001a + 10010b + 1100c
= 11.(9091a + 910b + 100c)
For N = 5:
“abcdeedcba” = 1000000000a + 100000000b + 10000000c + 1000000d + 100000e + 10000e + 1000d + 100c + 10b + a
= 1000000001a + 100000010b + 10000100c + 100100d + 110000e
= 11.(90909091a + 909091b + 91000c + 10000d)
Approach: From the above observation, a pattern can be observed that every palindrome product will always have a factor 11.
- For any N digit numbers P and Q, if the product of P and Q is a palindrome, then either P or Q is divisible by 11 but not both of them.
- Therefore, instead of checking whether the product of P and Q is a palindrome for all the possible pairs of P and Q, we can reduce the number of computations by checking only for the multiples of 11 for one of the numbers.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to check if a number is a// Palindrome or notbool isPalindrome(long x){ // Taking the string value // of the number string num = to_string(x); bool result = true; int i = 0; int j = num.length() - 1; // Loop to check if every i-th // character from beginning is // equal to every (N - i)th char while (i < j && result) { result = num[i++] == num[j--]; } return result;}// Function to find the largest palindrome// which is a product of two N digited numbersvoid find(int nDigits){ // Find lowerBound, upperBound for // a given nDigits. for n=2; [10, 99] long lowerBound = (long)pow(10, nDigits - 1); long upperBound = (lowerBound * 10) - 1; // Result variables long resultP = 0, resultQ = 0, resultR = 0; // Keep p decrementing by 11 for (long p = upperBound; p > lowerBound; p -= 11) { // Find the nearest number // divisible by 11 while (p % 11 != 0) { p--; } // Keep decrementing q by 1 for (long q = upperBound; q > lowerBound; q--) { long t = p * q; // Update the result if // t > r and is a palindrome if (t > resultR && isPalindrome(t)) { resultP = p; resultQ = q; resultR = t; break; } } } // Printing the readonly result cout << resultR << endl;}// Driver codeint main(){ int N = 2; find(N);}// This code is contributed by phasing17 |
Java
// Java implementation of the above approachpublic class GFG { // Function to check if a number is a // Palindrome or not static boolean isPalindrome(long x) { // Taking the string value // of the number String num = String.valueOf(x); boolean result = true; int i = 0; int j = num.length() - 1; // Loop to check if every i-th // character from beginning is // equal to every (N - i)th char while (i < j && result) { result = num.charAt(i++) == num.charAt(j--); } return result; } // Function to find the largest palindrome // which is a product of two N digited numbers public static void find(final int nDigits) { // Find lowerBound, upperBound for // a given nDigits. for n=2; [10, 99] final long lowerBound = (long)Math.pow(10, nDigits - 1); final long upperBound = (lowerBound * 10) - 1; // Result variables long resultP = 0, resultQ = 0, resultR = 0; // Keep p decrementing by 11 for (long p = upperBound; p > lowerBound; p -= 11) { // Find the nearest number // divisible by 11 while (p % 11 != 0) { p--; } // Keep decrementing q by 1 for (long q = upperBound; q > lowerBound; q--) { long t = p * q; // Update the result if // t > r and is a palindrome if (t > resultR && isPalindrome(t)) { resultP = p; resultQ = q; resultR = t; break; } } } // Printing the final result System.out.println(resultR); } // Driver code public static void main(String[] args) { int N = 2; find(N); }} |
Python3
# Python 3 implementation of # the above approach# Function to check if a # number is a Palindrome # or notdef isPalindrome(x): # Taking the string value # of the number num = str(x) result = True i = 0 j = len(num) - 1 # Loop to check if every i-th # character from beginning is # equal to every(N - i)th char while (i < j and result): result = num[i] == num[j] i += 1 j -= 1 return result# Function to find the largest # palindrome which is a product # of two N digited numbersdef find(nDigits): # Find lowerBound, upperBound # for a given nDigits. for n = 2 # [10, 99] lowerBound = pow(10, nDigits - 1) upperBound = (lowerBound * 10) - 1 # Result variables resultP = 0 resultQ = 0 resultR = 0 # Keep p decrementing by 11 for p in range(upperBound, lowerBound, -11): # Find the nearest number # divisible by 11 while (p % 11 != 0): p -= 1 # Keep decrementing q by 1 for q in range(upperBound, lowerBound, -1): t = p * q # Update the result if # t > r and is a palindrome if (t > resultR and isPalindrome(t)): resultP = p resultQ = q resultR = t break # Printing the final result print(resultR)# Driver codeif __name__ == "__main__": N = 2 find(N)# This code is contributed by Chitranayal |
C#
// C# implementation of the above approachusing System;class GFG { // Function to check if a number is a // Palindrome or not static bool isPalindrome(long x) { // Taking the string value // of the number String num = String.Join("",x); bool result = true; int i = 0; int j = num.Length - 1; // Loop to check if every i-th // character from beginning is // equal to every (N - i)th char while (i < j && result) { result = num[i++] == num[j--]; } return result; } // Function to find the largest palindrome // which is a product of two N digited numbers public static void find(int nDigits) { // Find lowerBound, upperBound for // a given nDigits. for n=2; [10, 99] long lowerBound = (long)Math.Pow(10, nDigits - 1); long upperBound = (lowerBound * 10) - 1; // Result variables long resultP = 0, resultQ = 0, resultR = 0; // Keep p decrementing by 11 for (long p = upperBound; p > lowerBound; p -= 11) { // Find the nearest number // divisible by 11 while (p % 11 != 0) { p--; } // Keep decrementing q by 1 for (long q = upperBound; q > lowerBound; q--) { long t = p * q; // Update the result if // t > r and is a palindrome if (t > resultR && isPalindrome(t)) { resultP = p; resultQ = q; resultR = t; break; } } } // Printing the readonly result Console.WriteLine(resultR); } // Driver code public static void Main(String[] args) { int N = 2; find(N); }}// This code is contributed by sapnasingh4991 |
Javascript
<script>// Javascript implementation of the above approach // Function to check if a number is a // Palindrome or not function isPalindrome(x) { // Taking the string value // of the number let num = x.toString(); let result = true; let i = 0; let j = num.length - 1; // Loop to check if every i-th // character from beginning is // equal to every (N - i)th char while (i < j && result) { result = num[i++] == num[j--]; } return result; } // Function to find the largest palindrome // which is a product of two N digited numbers function find(nDigits) { // Find lowerBound, upperBound for // a given nDigits. for n=2; [10, 99] let lowerBound = Math.floor(Math.pow(10, nDigits - 1)); let upperBound = (lowerBound * 10) - 1; // Result variables let resultP = 0, resultQ = 0, resultR = 0; // Keep p decrementing by 11 for (let p = upperBound; p > lowerBound; p -= 11) { // Find the nearest number // divisible by 11 while (p % 11 != 0) { p--; } // Keep decrementing q by 1 for (let q = upperBound; q > lowerBound; q--) { let t = p * q; // Update the result if // t > r and is a palindrome if (t > resultR && isPalindrome(t)) { resultP = p; resultQ = q; resultR = t; break; } } } // Printing the readonly result document.write(resultR); }// Driver Code let N = 2; find(N); </script> |
Output:
9009
Time Complexity: O(upperBound – lowerBound)2
Auxiliary Space: O(1)
Related Article: Largest palindrome which is product of two n-digit numbers
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
