Last active
September 15, 2018 06:36
-
-
Save Buggytheclown/f6220389980bb6365d43fa6a6c2b6837 to your computer and use it in GitHub Desktop.
Largest palindrome that is product of 2 prime 5 digit number
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const MAX_DIVISOR = 99999; | |
const MIN_DIVISOR = 10000; | |
function isPalindrome(number) { | |
let rebmun = 0; | |
let remainder = number; | |
while (remainder !== 0) { | |
let lastDigit = remainder % 10; | |
rebmun = rebmun * 10 + lastDigit; | |
remainder = (remainder - lastDigit) / 10; | |
} | |
return number === rebmun; | |
} | |
function getPrimeDivisors(oddNumber) { | |
if (oddNumber % 2 === 0) return []; | |
for (let i = 3; i <= Math.sqrt(oddNumber); i += 2) { | |
if (oddNumber % i === 0) { | |
if (i < MIN_DIVISOR) { | |
return []; | |
} else { | |
return [i, oddNumber / i]; | |
} | |
} | |
} | |
return []; | |
} | |
function getMaxPalindrome(fromOdd) { | |
while (!isPalindrome(fromOdd)) { | |
fromOdd -= 2; | |
} | |
return fromOdd; | |
} | |
function getPrevPalindrome(palindrome) { | |
function digitsCount(number) { | |
let count = 0; | |
while (number !== 0) { | |
count++; | |
number = ~~(number / 10); | |
} | |
return count; | |
} | |
function calcPalindrome(num, count) { | |
let partToMerge = count % 2 ? ~~(num / 10) : num; | |
while (partToMerge) { | |
let lastDigit = partToMerge % 10; | |
num = num * 10 + lastDigit; | |
partToMerge = (partToMerge - lastDigit) / 10; | |
} | |
return num; | |
} | |
const palindromeLength = digitsCount(palindrome); | |
const newFirstPart = ~~(palindrome / Math.pow(10, ~~(palindromeLength / 2))) - 1; | |
const prevPalindrome = calcPalindrome(newFirstPart, palindromeLength); | |
return palindromeLength > digitsCount(prevPalindrome) ? (prevPalindrome * 10 + 9) : prevPalindrome; | |
} | |
function main() { | |
let palindrome = getMaxPalindrome(MAX_DIVISOR * MAX_DIVISOR); | |
let divisors = getPrimeDivisors(palindrome); | |
while (divisors.length !== 2) { | |
palindrome = getPrevPalindrome(palindrome); | |
divisors = getPrimeDivisors(palindrome); | |
} | |
return {palindrome, divisors}; | |
} | |
// ********** another file.js ********** | |
console.time('main'); | |
eq(main(), {palindrome: 999949999, divisors: [30109, 33211]}); | |
// console.log(main()); | |
console.timeEnd('main'); | |
// runTests(); | |
function eq(obj1, obj2, txt = 'Eq fail') { | |
const isEq = JSON.stringify(obj1) === JSON.stringify(obj2); | |
if (isEq) { | |
return true; | |
} else { | |
console.log('expect eq: '); | |
if (Array.isArray(obj1) && Array.isArray(obj2)) { | |
for (let i = 0; i < obj1.length; i++) { | |
if (obj1[i] !== obj2[i]) { | |
console.log(`${obj1[i]} !== ${obj2[i]}`); | |
} | |
} | |
} else { | |
console.log(obj1); | |
console.log(obj2); | |
} | |
throw new Error(txt); | |
} | |
} | |
function runTests() { | |
(function () { | |
console.log('__isPolindrome__: START'); | |
const truthy = [997799, 996699, 995599, 994499, 993399, 992299, 991199, 990099, 989989, 988889, 987789, 986689, 985589, 984489, 983389, 982289, 981189, 980089, 979979, 978879]; | |
const falsy = [9799, 9916699, 1995599, 9944991, 9923399, 9922919, 9901199, 9090099, 9189989, 988189, 97789, 981689, 9815589, 1984489, 9833891, 1982289, 9081189, 9089, 11110000, 11100]; | |
truthy.forEach(el => eq(isPalindrome(el), true, `must be a isPolindrome: ${el}`)); | |
falsy.forEach(el => eq(isPalindrome(el), false, `must not be a isPolindrome: ${el}`)); | |
console.log('__isPolindrome__: COMPLETED'); | |
})(); | |
(function () { | |
console.log('__getPrimeDivisors__: START'); | |
let mock = [ | |
{divisors: [65327, 153073], num: 9999799871}, | |
{divisors: [34429, 290447], num: 9999799763}, | |
{divisors: [31513, 317323], num: 9999799699}, | |
{divisors: [15679, 637783], num: 9999799657}, | |
{divisors: [87433, 114371], num: 9999799643}, | |
{divisors: [39323, 254299], num: 9999799577}, | |
{divisors: [16301, 613447], num: 9999799547}, | |
{divisors: [15359, 651071], num: 9999799489}, | |
{divisors: [11503, 869321], num: 9999799463}, | |
{divisors: [11527, 867511], num: 9999799297}, | |
{divisors: [79349, 126023], num: 9999799027} | |
]; | |
mock.forEach(({divisors, num}) => eq(getPrimeDivisors(num), divisors)); | |
console.log('__getPrimeDivisors__: COMPLETED'); | |
})(); | |
(function () { | |
console.log('__getPalindromes__: START'); | |
const palindroms = []; | |
const from = 999 * 999; | |
const to = 101 * 101; | |
for (let i = from; i > to; i -= 1) { | |
if (isPalindrome(i)) palindroms.push(i); | |
} | |
const palindroms2 = []; | |
for (let i = getMaxPalindrome(from); i > to; i = getPrevPalindrome(i)) { | |
palindroms2.push(i); | |
} | |
eq(palindroms, palindroms2, 'getPrevPalindrome err'); | |
console.log('__getPalindromes__: COMPLETED'); | |
})(); | |
console.log('!!__SUCESS__!!'); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment