Given a positive integer N, the task is to find the largest palindromic number less than N and it can be expressed as the product of two 3-digit numbers.
Examples:
Input: N = 101110
Output: 101101
Explanation: The number 101101 ( = 143 * 707) is the largest palindromic number possible satisfying the conditions.Input: N = 800000
Output: 793397
Explanation: The number 793397 ( = 869 × 913) is the largest palindromic number possible satisfying the conditions.
Naive Approach: The simplest generate all possible pairs from the range [100, 999] and for each pair, check if their product is a palindrome or not and is less than N or not. Print the maximum of all such products obtained as the required answer.
Time Complexity: O(N * 9002)
Auxiliary Space: O(1)
Alternate Approach: The problem can also be solved based on the observation that all the multiples of 11 are palindromes. Therefore, iterate over the range [100, 999] and for every value in the range, iterate over the multiples of 11 in the range [121, 999], and check for the required condition in each iteration. Follow the steps below to solve the problem:
- Initialize a variable, say num, to store the largest palindromic number satisfying the given conditions.
- Iterate over the range [100, 999] using a variable, say i, and perform the following steps:
- Iterate over the range [121, 999] using a variable, say j in multiples of 11.
- Store the product of i and j in string x.
- If the value of X is less than N and X is a palindrome, then update the value of num if X > num.
- Otherwise, keep iterating for the next pair of integers.
- Iterate over the range [121, 999] using a variable, say j in multiples of 11.
- After the above steps, print the value of num.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the largest palindrome// not exceeding N which can be expressed// as the product of two 3-digit numbersvoid palindrome_prod(string N){ // Stores all palindromes vector<int> palindrome_list; for (int i = 101; i < 1000; i++) { for (int j = 121; j < 1000; j += (i % 11 == 0) ? 1 : 11) { // Stores the product int n = i * j; string x = to_string(n); string y = x; reverse(y.begin(), y.end()); // Check if X is palindrome if (x == y){ // Check n is less than N if (n < stoi(N)){ // If true, append it // in the list palindrome_list.push_back(i * j); } } } } // Print the largest palindrome cout << (*max_element(palindrome_list.begin(), palindrome_list.end()));}// Driver Codeint main(){ string N = "101110"; // Function Call palindrome_prod(N); return 0;}// This code is contributed by mohit kumar 29 |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the largest palindrome// not exceeding N which can be expressed// as the product of two 3-digit numbersstatic void palindrome_prod(String N){ // Stores all palindromes Vector<Integer> palindrome_list = new Vector<Integer>(); for (int i = 101; i < 1000; i++) { for (int j = 121; j < 1000; j += (i % 11 == 0) ? 1 : 11) { // Stores the product int n = i * j; String x = String.valueOf(n); String y = x; reverse(y); // Check if X is palindrome if (x == y){ // Check n is less than N if (n < Integer.valueOf(N)){ // If true, append it // in the list palindrome_list.add(i * j); } } } } // Print the largest palindrome System.out.print(Collections.max(palindrome_list));}static String reverse(String input) { char[] a = input.toCharArray(); int l, r = a.length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.valueOf(a);} // Driver Codepublic static void main(String[] args){ String N = "101110"; // Function Call palindrome_prod(N);}}// This code is contributed by 29AjayKumar |
Python3
# Python program for the above approach# Function to find the largest palindrome# not exceeding N which can be expressed# as the product of two 3-digit numbersdef palindrome_prod(N): # Stores all palindromes palindrome_list = [] for i in range(101, 1000): for j in range(121, 1000, (1 if i % 11 == 0 else 11)): # Stores the product n = i * j x = str(n) # Check if X is palindrome if x == x[::-1]: # Check n is less than N if n < N: # If true, append it # in the list palindrome_list.append(i * j) # Print the largest palindrome print(max(palindrome_list))# Driver CodeN = 101110# Function Callpalindrome_prod(N) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;using System.Linq;class GFG{// Function to find the largest palindrome// not exceeding N which can be expressed// as the product of two 3-digit numbersstatic void palindrome_prod(String N){ // Stores all palindromes List<int> palindrome_list = new List<int>(); for (int i = 101; i < 1000; i++) { for (int j = 121; j < 1000; j += (i % 11 == 0) ? 1 : 11) { // Stores the product int n = i * j; String x = String.Join("", n); String y = x; reverse(y); // Check if X is palindrome if (x == y) { // Check n is less than N if (n < Int32.Parse(N)) { // If true, append it // in the list palindrome_list.Add(i * j); } } } } // Print the largest palindrome Console.Write(palindrome_list.Max());}static String reverse(String input) { char[] a = input.ToCharArray(); int l, r = a.Length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.Join("", a);} // Driver Codepublic static void Main(String[] args){ String N = "101110"; // Function Call palindrome_prod(N);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program for the above approach// Function to find the largest palindrome// not exceeding N which can be expressed// as the product of two 3-digit numbersfunction palindrome_prod(N){ // Stores all palindromes var palindrome_list = []; var i,j; for (i = 101; i < 1000; i++) { for (j = 121; j < 1000; j += (i % 11 == 0) ? 1 : 11) { // Stores the product var n = i * j; var x = n.toString(); var y = x; y = y.split("").reverse().join(""); // Check if X is palindrome if (x == y){ // Check n is less than N if (n < Number(N)){ // If true, append it // in the list palindrome_list.push(i * j); } } } } // Print the largest palindrome document.write(Math.max.apply(null, palindrome_list));}// Driver Code var N = "101110"; // Function Call palindrome_prod(N);</script> |
Output:
101101
Time Complexity: O(N*9002)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
