Largest palindrome which is product of two N-digit numbers : Set 2

0 0 7 minutes read

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 not
bool 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 numbers
void 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 code
int main()
{
    int N = 2;
    find(N);
}
 
// This code is contributed by phasing17

Java

// Java implementation of the above approach
 
public 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 not
def 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 numbers
def 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 code
if __name__ == "__main__":
 
    N = 2
    find(N)
 
# This code is contributed by Chitranayal

C#

// C# implementation of the above approach
using 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:

Time Complexity: O(upperBound – lowerBound)²

Auxiliary Space: O(1)

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 zambiatek!