Here's mine in Python 3 :) It's a bit more complicated because I try to write them more flexible. Like how this problem shows 2 digit numbers as an example and 3 for the actual problem, so I wrote it to take the number of digits per number as an input
Not linear... but I think (without any actual proof 🤷♂️) (I'm a fraud 🤦♂️) that my solution does it in logarithmic time: dev.to/maxart2501/comment/b9m6
Edit: scratch that, no way it's not quadratic 😂 But then again, it's faster than the extensive check.
Here's my Ruby solution. There's probably a much more clever way to do this. Probably a more Ruby way to do it for that matter.
# Find the largest palindrome number that is the product of two three digit factors.defcheck_equality(num)num.to_s==num.to_s.reverseenddeffind_palindromer1=(999..1)r2=r1(r1.first).downto(r1.last).eachdo|i|(r2.first).downto(r2.last).eachdo|j|ifcheck_equality(i*j)puts"#{i} * #{j} = #{i*j}"returnendendendendfind_palindrome
If I understand it correctly (correct me if I'm wrong, I don't know Ruby), this doesn't work in general, as it prints the first palindrome product you find. But you don't know if it's the largest.
I'm working backwards through the range of numbers beginning with '999.' Hence the extra verbosity in the block with the call to the downto method. (999..1).each do doesn't work, and (1..999).each do really shouldn't work either because ranges are not defined by their content, just a beginning state and an end state. So counting backwards the first palindrome I find is the largest. And the outer block isn't necessary, but I include it just for the sake of being thorough I guess.
The problem here is that the products you're getting aren't ordered. Which means that if you get a palindrome, you cannot be sure it's the largest.
In fact, I run your code and I got 999 * 91 = 90909, which is not correct. Even if you limit your range to 999 to 100 (we're looking for 3-digit factors after all), you'd get 995 * 583 = 580085. But the largest palindrome is 993 * 913 = 906609, which comes after the others.
functionreverseInteger(n:number):number{returnNumber(String(n).split('').reverse().join(''));}functionisPalindrome(num:number):boolean{if(num===reverseInteger(num)){returntrue;}returnfalse;}// I had this in separate files sorry if its confusing X)import{max}from'mathjs';letnumber=0;leta=999;constpalindromes:number[]=[];while(a>1){for(leti=2;i<=999;i+=1){number=a*i;if(isPalindrome(number)){palindromes.push(number);}}a-=1;}console.log(`Max palindrome ${max(...palindromes)}`);
while there are many explanations, easiest to understand was yours. the only part I struggle to understand is this one "isPalindrome(product) && product > largestPalindrome", can you please explain what it means?
We first check if the product is a palindrome. Because if it isn't, we don't care about it.
Then, we check if it is greater than our existing largest palindrome because our goal is to find the largest palindrome.
If both those conditions are true, the product being a palindrome and it being larger than our existing largest palindrome, we set that as our largest palindrome.
Hope that helps, let me know if you still have questions!
publicclassProblem4{publicstaticbooleanisPalindrome(longval){booleanisPalindrome=true;Stringstr=Long.toString(val);intlen=str.length();inti=0;while(isPalindrome&&i<=(len-1)/2){isPalindrome=str.charAt(i)==str.charAt(len-1-i);i++;}returnisPalindrome;}publicstaticvoidmain(String[]args){inti=999;longlargest=1;Stringstr="";longval=1;while(i>=100){intj=i;while(j>=100){val=i*j;if(isPalindrome(val)&&largest<val){largest=val;str=i+" x "+j;}isPalindrome(val);j--;}i--;}System.out.println(str+"= "+largest);}}
x=0# assuming number is Xnnnnn 1st digit
y=0# assuming number is nYnnnn 2nd digit
z=0# assuming number is nnZnnn 3rd digit
num=999#highest 3 digit number
palidromefound=Falsehighestnum=num*numwhilestr(highestnum)!=str(highestnum)[::-1]:z=int(highestnum/1000)z=z%10y=int(highestnum/10000)y=y%10x=int(highestnum/100000)x=x%10ifz!=0andy!=0:z=z-1# first time find the highest palidrom
highestnum=(x*100000+y*10000+z*1000+z*100+y*10+x)whilepalidromefound==False:ifstr(highestnum)==str(highestnum)[::-1]:whilenum>99:if(highestnum%num)==0and(highestnum/num)<999and(highestnum/num)>99:palidromefound=Trueprint(f'Highest Palidrom: {highestnum} num1: {num} and num2: {int(highestnum / num)}')breaknum=num-1else:num=999# below are the palidromes.. the value of z is the 3rd digit, it comes from the above logic
# when the first highest palidrom is found, but if it not a multiple of two three digit numbers
# then the next highest palidrome is obtained:
#
# 992299 - 1100 = 991199 >> when z != 0
# 991199 - 1100 = 990099 >> when z != 0
# 990099 - 110 = 989989 >> when z == 0
# 989989 - 1100 = 988889 >> when z != 0
ifz==0:highestnum=highestnum-110z=9else:highestnum=highestnum-1100z=z-1
Love to work on the challenges, please keep this series running.
Here's my Rust Solution: Playground
fnmain(){letmax=max_palindrome();println!("Max palindrome is {}, product of {} * {}",max.1,(max.0).0,(max.0).1);}fnmax_palindrome()->((i32,i32),i32){letrange=100..1000;letmutans=((0,0),0);forainrange.clone(){forbinrange.clone(){letp=a*b;ifis_palindrome(p)&&p>ans.1{ans.1=p;ans.0=(a,b);}}}ans}fnis_palindrome(num:i32)->bool{letstr_num=num.to_string();str_num.chars().zip(str_num.chars().rev()).all(|(c1,c2)|c1==c2)}
Sooo... there are so many good solutions, but they all kind of look the same, so I wanted a different approach 😁
What if, instead of starting with the factors and checking if their product is a palindrome, we start with palindromes and find two 3-digit factors?
We'd start with 999999, then 998899, then 997799... You get the point. So we can start with a 3-digit number (e.g. 356)... and get a palindrome out of it (e.g. 356653), and look for factors.
I've tested it with up to 7 digits and it's still basically instantaneous. Over that limit you go over Number.MAX_SAFE_INTEGER and it becomes unreliable. I didn't bother using BigInts, also because you can't get the square root out of them (you can approximate it, but it's a bother).
P.S.: yes, I've used a label in JavaScript. Sue me 😂 (also useful if you have to break out of more than one cycle... which is usually rare).
First observation is that the number must be between 100^2 and 999^2 or in the range of [10000, 998001].
As the majority of numbers has 6 digits and we're looking for the largest, we ignore 5 digits numbers.
Based on this, we can construct a palindromic number as:
'abccba' =100000a+10000b+1000c+100c+10b+a
=100001a+10010b+1100c
=11(9091a+910b+100c) = p.q
This equation shows us, that either p or q, but not both must have a factor of 11!!!
def palindrome_number(x,y):
my_list =[]
for i in range(x,y):
for j in range(x,y):
num = i * j
if num % 11 ==0 and str(num) == str(num)[::-1]:
my_list.append(num)
my_list.sort()
print(my_list[-1])
function largestPalindromeProduct(n) {
let num = "1"
let lNumber = 0
for(let i = 0; i < n; i++){
num = ${num}0
}
num = parseInt(num)
let rangeNum = num.toString().replace("0","")
lNumberLoop:
for(let i = num; i > 0 ; i--){
for(let j = i; j > i - rangeNum; j --){
let number = (i * j)
let revN = parseInt(number.toString().split("").reverse().join(""))
if(number === revN && revN.toString().length % 2 === 0){
lNumber = number
break lNumberLoop
}
}
}
return lNumber
}
functionlargestPalindromeProduct(n){// Good luck!constisPalindrom=n=>{returnString(n).split("").reverse().join("")===String(n);}letlargestPalindrome=0;constlowerBound=Number(`1${Array.from({length:n}).join(0)}`);constupperBound=Number(`${Array.from({length:n+1}).join(9)}`);console.log({upperBound,lowerBound})for(vari=lowerBound;i<=upperBound;i++){for(varj=lowerBound;j<=upperBound;j++){constproduct=i*j;if(isPalindrom(product)&&product>largestPalindrome){console.log(i,j,product,largestPalindrome)largestPalindrome=i*j;}}}returnlargestPalindrome;}largestPalindromeProduct(2);
This is another solution that I consider working in this particular case (3 digits) but not actually correct in the general case. I explained it here: dev.to/maxart2501/comment/b9me
This is another solution that I consider working in this particolar case (3 digits) but not actually correct (granted I could understand F# 😅). I explained it here: dev.to/maxart2501/comment/b9me
I'm sorry if that seemed rude, that wasn't my intention at all. I did add "granted I could understand F#" in case I was wrong.
But no, I will keep on trying to understand what's going on in other people's code even out of my comfort zone, because I'll have the chance to learn something new 👌
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
This is the easiest way and logical too..
list = []
for i in range(901,1000):
for j in range(901,1000):
prod = i*j
if str(prod) == str(prod)[::-1]:
list.append(prod)
i += 1
j += 1
list.sort()
print(list[-1])
Did you try hackerrank's version? They have broader ranges for input values and pretty tight time/memory limitations. That sometimes makes even trivial project euler tasks challenging. :)
Here's my Python solution!
How's the run time? I think yours is Python 2?
Here's mine in Python 3 :) It's a bit more complicated because I try to write them more flexible. Like how this problem shows 2 digit numbers as an example and 3 for the actual problem, so I wrote it to take the number of digits per number as an input
A quadratic solution in JavaScript. I'm curious if there's a way to do this in linear time:
Not linear... but I think (without any actual proof 🤷♂️) (I'm a fraud 🤦♂️) that my solution does it in logarithmic time: dev.to/maxart2501/comment/b9m6
Edit: scratch that, no way it's not quadratic 😂 But then again, it's faster than the extensive check.
Here's my Ruby solution. There's probably a much more clever way to do this. Probably a more Ruby way to do it for that matter.
If I understand it correctly (correct me if I'm wrong, I don't know Ruby), this doesn't work in general, as it prints the first palindrome product you find. But you don't know if it's the largest.
Unless you can prove it is 🤷♂️ (I have no idea).
I'm working backwards through the range of numbers beginning with '999.' Hence the extra verbosity in the block with the call to the downto method. (999..1).each do doesn't work, and (1..999).each do really shouldn't work either because ranges are not defined by their content, just a beginning state and an end state. So counting backwards the first palindrome I find is the largest. And the outer block isn't necessary, but I include it just for the sake of being thorough I guess.
The problem here is that the products you're getting aren't ordered. Which means that if you get a palindrome, you cannot be sure it's the largest.
In fact, I run your code and I got
999 * 91 = 90909, which is not correct. Even if you limit your range to 999 to 100 (we're looking for 3-digit factors after all), you'd get995 * 583 = 580085. But the largest palindrome is993 * 913 = 906609, which comes after the others.My typescript solution:
Please don't do this 😕 It's verbose for no reason. You can accomplish the same with just
return condition;.cool! yes so much simple
thanks!
Just did this super quick in JS.
while there are many explanations, easiest to understand was yours. the only part I struggle to understand is this one "isPalindrome(product) && product > largestPalindrome", can you please explain what it means?
Yes. Let's try reading it step by step:
Hope that helps, let me know if you still have questions!
Thank you, Faraz, I didn't know it was possible to use several conditional operators in one single line of code
Here is my code on C (Brute force), the result was out after 0.172s.
Written in Java!
Solution in Python:
Love to work on the challenges, please keep this series running.
Here's my Rust Solution: Playground
Sooo... there are so many good solutions, but they all kind of look the same, so I wanted a different approach 😁
What if, instead of starting with the factors and checking if their product is a palindrome, we start with palindromes and find two 3-digit factors?
We'd start with 999999, then 998899, then 997799... You get the point. So we can start with a 3-digit number (e.g. 356)... and get a palindrome out of it (e.g. 356653), and look for factors.
My solution in JavaScript:
I've tested it with up to 7 digits and it's still basically instantaneous. Over that limit you go over
Number.MAX_SAFE_INTEGERand it becomes unreliable. I didn't bother usingBigInts, also because you can't get the square root out of them (you can approximate it, but it's a bother).P.S.: yes, I've used a label in JavaScript. Sue me 😂 (also useful if you have to break out of more than one cycle... which is usually rare).
First observation is that the number must be between 100^2 and 999^2 or in the range of [10000, 998001].
As the majority of numbers has 6 digits and we're looking for the largest, we ignore 5 digits numbers.
Based on this, we can construct a palindromic number as:
'abccba' =100000a+10000b+1000c+100c+10b+a
=100001a+10010b+1100c
=11(9091a+910b+100c) = p.q
This equation shows us, that either p or q, but not both must have a factor of 11!!!
def palindrome_number(x,y):
void solve()
{
fast;
ll n,largepalin=0;
cin>>n;
for(ll i=999;i>=100;i--)
{
for(ll j=999;j>=100;j--)
{
if((i*j)%11==0 && palin(i*j) && (i*j)<n) largepalin=max(i*j,largepalin);
}
}
cout<<largepalin<<endl;
return;
}
a lazy c++ solution :)
This is my solution in Javascript
function largestPalindromeProduct(n) {
let num = "1"
let lNumber = 0
for(let i = 0; i < n; i++){
num =
${num}0}
num = parseInt(num)
let rangeNum = num.toString().replace("0","")
lNumberLoop:
for(let i = num; i > 0 ; i--){
for(let j = i; j > i - rangeNum; j --){
let number = (i * j)
let revN = parseInt(number.toString().split("").reverse().join(""))
if(number === revN && revN.toString().length % 2 === 0){
lNumber = number
break lNumberLoop
}
}
}
return lNumber
}
console.log(largestPalindromeProduct(2));
Here is freeCodeCamp version of it
Am still able to just copy and paste from my Euler GitHub repo. 😂
PHP again
This is another solution that I consider working in this particular case (3 digits) but not actually correct in the general case. I explained it here: dev.to/maxart2501/comment/b9me
C#
This is another solution that I consider working in this particolar case (3 digits) but not actually correct (granted I could understand F# 😅). I explained it here: dev.to/maxart2501/comment/b9me
I'm sorry if that seemed rude, that wasn't my intention at all. I did add "granted I could understand F#" in case I was wrong.
But no, I will keep on trying to understand what's going on in other people's code even out of my comfort zone, because I'll have the chance to learn something new 👌
Complete Solution..!!! for Euler 004
void solve()
{
fast;
ll n,largepalin=0;
cin>>n;
for(ll i=999;i>=100;i--)
{
for(ll j=999;j>=100;j--)
{
if((i*j)%11==0 && palin(i*j) && (i*j)<n) largepalin=max(i*j,largepalin);
}
}
cout<<largepalin<<endl;
return;
}
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
This is the easiest way and logical too..
Did you try hackerrank's version? They have broader ranges for input values and pretty tight time/memory limitations. That sometimes makes even trivial project euler tasks challenging. :)
here is my result using JS. avoided any use of methods. Also not a master in mathematics but here it is
Being wrong is nothing to be ashamed of, as long as you're ready to stand corrected.
My mistake in this case is that I commented while it was very late 😴 Took note on the approach, though.