Inhalt
Die Fakten:
| Plattform: | codewars.com |
| Name: | A Rule of Divisibility by 13 |
| Level: | 6 kyu |
| Sprache: | TypeScript |
Beschreibung:
From Wikipedia:
"A divisibility rule is a shorthand way of determining whether a given integer is divisible by a fixed divisor without performing the division, usually by examining its digits."
When you divide the successive powers of 10 by 13 you get the following remainders of the integer divisions:
1, 10, 9, 12, 3, 4 because:
10 ^ 0 -> 1 (mod 13)
10 ^ 1 -> 10 (mod 13)
10 ^ 2 -> 9 (mod 13)
10 ^ 3 -> 12 (mod 13)
10 ^ 4 -> 3 (mod 13)
10 ^ 5 -> 4 (mod 13)
(For "mod" you can see: )
Then the whole pattern repeats. Hence the following method:
Multiply
- the right most digit of the number with the left most number in the sequence shown above,
- the second right most digit with the second left most digit of the number in the sequence.
The cycle goes on and you sum all these products. Repeat this process until the sequence of sums is stationary.
Example:
What is the remainder when 1234567 is divided by 13?
7 6 5 4 3 2 1 (digits of 1234567 from the right)
× × × × × × × (multiplication)
1 10 9 12 3 4 1 (the repeating sequence)
Therefore following the method we get:
7×1 + 6×10 + 5×9 + 4×12 + 3×3 + 2×4 + 1×1 = 178
We repeat the process with the number 178:
8x1 + 7x10 + 1x9 = 87
and again with 87:
7x1 + 8x10 = 87
From now on the sequence is stationary (we always get 87) and the remainder of 1234567 by 13 is
the same as the remainder of 87 by 13 ( i.e 9).
Task:
Call thirt the function which processes this sequence of operations on an integer n (>=0). thirt will return the stationary number.
thirt(1234567) calculates 178, then 87, then 87 and returns 87.
thirt(321) calculates 48, 48 and returns 48
Quelle: codewars.com
Lösung
Pseudo-Code
Erst die Lösungsschritte in Pseudo-Code. Los geht’s:
Lösungsschritte
Schritt 1
Als erstes speichern wir uns die Remainder-Sequenz in einer Variablen
Schritt 2
Dann brauchen wir einen Loop! ⭕
Schritt 3
In jeder Iteration drehen wir die Ziffern der aktuellen Zahl um
Schritt 4
Dann berechnen wir für jede Ziffer das Produkt mit der aktuellen Zahl aus der Remainder-Sequenz
Schritt 5
Und können dann die Summe dieser Produkte berechnen
Schritt 6
Wenn die aktuelle Zahl dieser Summe entspricht, können wir den Loop beenden
Code
Geil. Übersetzen wir unseren Pseudo-Code in TypeScript:
Lösungsschritte
Meine erste Zeile (ich habe n in num umbenannt):
export function thirt(num: number): number {
Dann speichern wir uns die Remainder-Sequenz in eine Variable:
const sequence = [1, 10, 9, 12, 3, 4];
Außerdem lege ich mir noch 2 weitere Variablen für die aktuelle Zahl und die aktuelle Summe an:
let currNum = num;
let currSum = 0;
So ist sichergestellt, dass die Input-Zahl durch diese Funktion nicht verändert wird (Immutabilität).
Dann der Loop:
while (true) {
Ich entscheide mich hier für einen unbedingten, unendlichen while-Loop.
Jetzt setze ich die aktuelle Zahl:
if (currSum) currNum = currSum;
Wir haben die Summe mit 0 initialisiert. Darum ist die aktuelle Zahl im ersten Durchlauf die Input-Zahl (num), danach entspricht sie der aktuellen Summe.
Jetzt können wir die Ziffern der aktuellen Zahl umdrehen:
const revDigits = [...String(currNum)].reverse().map(Number);
Und jetzt die Summe der Produkte der Ziffern und der aktuellen Sequenz-Zahl berechnen:
currSum = revDigits.reduce((sum, digit, i) => sum + digit * sequence[i % 6], 0);
Für mich macht es in diesem Fall keinen Sinn die Sequenz-Länge (6) dynamisch zu halten. Darum habe ich sie hier hardgecodet. Du kann natürlich auch gerne sequence.length verwenden.
Wenn die aktuelle Zahl der aktuellen Summe entspricht, können wir die aktuelle Zahl zurückgeben und damit auch den Loop beenden:
if (currNum === currSum) return currNum;
}
}
Voilá! 💪
Komplettlösung
export function thirt(num: number): number {
const sequence = [1, 10, 9, 12, 3, 4]; // length: 6
let currNum = num;
let currSum = 0;
while (true) {
if (currSum) currNum = currSum;
const revDigits = [...String(currNum)].reverse().map(Number);
currSum = revDigits.reduce(
(sum, digit, i) => sum + digit * sequence[i % 6],
0,
);
if (currNum === currSum) return currNum;
}
}