Files
freeCodeCamp/curriculum/challenges/chinese/10-coding-interview-prep/project-euler/problem-92-square-digit-chains.md
2022-04-01 02:01:59 +09:00

154 lines
3.8 KiB
Markdown
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

---
id: 5900f3c81000cf542c50fedb
title: '问题 92平方数链'
challengeType: 5
forumTopicId: 302209
dashedName: problem-92-square-digit-chains
---
# --description--
将一个数字的每一位求平方再相加可以得到一个新的数字,不断重复该过程,直到新的数字出现过为止,可以得到一条数链。
举个例子:
$$\begin{align} & 44 → 32 → 13 → 10 → \boldsymbol{1} → \boldsymbol{1}\\\\
& 85 → \boldsymbol{89} → 145 → 42 → 20 → 4 → 16 → 37 → 58 → \boldsymbol{89}\\\\ \end{align}$$
可以发现,每条到达 1 或 89 的数链都会陷入循环。 最令人惊讶的是,从任意数字开始,数链最终都会到达 1 或 89。
求出有多少个小于 `limit` 的数字最终会到达 89
# --hints--
`squareDigitChains(100)` 应该返回一个数字。
```js
assert(typeof squareDigitChains(100) === 'number');
```
`squareDigitChains(100)` 应该返回 `80`
```js
assert.strictEqual(squareDigitChains(100), 80);
```
`squareDigitChains(1000)` 应该返回 `857`
```js
assert.strictEqual(squareDigitChains(1000), 857);
```
`squareDigitChains(100000)` 应该返回 `85623`
```js
assert.strictEqual(squareDigitChains(100000), 85623);
```
`squareDigitChains(10000000)` 应该返回 `8581146`
```js
assert.strictEqual(squareDigitChains(10000000), 8581146);
```
# --seed--
## --seed-contents--
```js
function squareDigitChains(limit) {
return true;
}
squareDigitChains(100);
```
# --solutions--
```js
function squareDigitChains(limit) {
// Based on https://www.xarg.org/puzzle/project-euler/problem-92/
function getCombinations(neededDigits, curDigits) {
if (neededDigits === curDigits.length) {
return [curDigits];
}
const combinations = [];
const lastDigit = curDigits.length !== 0 ? curDigits[0] : 9;
for (let i = 0; i <= lastDigit; i++) {
const results = getCombinations(neededDigits, [i].concat(curDigits));
combinations.push(...results);
}
return combinations;
}
function getPossibleSums(limit) {
const digitsCount = getDigits(limit).length - 1;
const possibleSquaredSums = [false];
for (let i = 1; i <= 81 * digitsCount; i++) {
let curVal = i;
while (curVal !== 1 && curVal !== 89) {
curVal = addSquaredDigits(curVal);
}
possibleSquaredSums[i] = curVal === 89;
}
return possibleSquaredSums;
}
function addSquaredDigits(num) {
const digits = getDigits(num);
let result = 0;
for (let i = 0; i < digits.length; i++) {
result += digits[i] ** 2;
}
return result;
}
function getDigits(number) {
const digits = [];
while (number > 0) {
digits.push(number % 10);
number = Math.floor(number / 10);
}
return digits;
}
function getFactorials(number) {
const factorials = [1];
for (let i = 1; i < number; i++) {
factorials[i] = factorials[i - 1] * i;
}
return factorials;
}
const neededDigits = getDigits(limit).length - 1;
const combinations = getCombinations(neededDigits, []);
const possibleSquaredDigitsSums = getPossibleSums(limit);
const factorials = getFactorials(neededDigits + 1);
let endingWith89 = 0;
for (let i = 0; i < combinations.length; i++) {
let counts = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
let digits = combinations[i];
let curSum = 0;
for (let j = 0; j < digits.length; j++) {
const curDigit = digits[j];
curSum += curDigit ** 2;
counts[curDigit]++;
}
if (possibleSquaredDigitsSums[curSum]) {
let denominator = 1;
for (let j = 0; j < counts.length; j++) {
denominator = denominator * factorials[counts[j]];
}
endingWith89 += Math.floor(
factorials[factorials.length - 1] / denominator
);
}
}
return endingWith89;
}
```