Inhalt
Die Fakten:
Plattform: | codewars.com |
Name: | Basics 08: Find next higher number with same Bits (1's) |
Level: | 6 kyu |
Sprache: | TypeScript |
Beschreibung:
Your task is to find the next higher number (int) with the same number of '1'- Bits.
I.e. as many 1
bits as before and output next higher than input. Input is always an int between 1 and 1<<30 (possibly inclusive). No bad cases or special tricks...
Some easy examples:
Input: 129 => Output: 130 (10000001 => 10000010)
Input: 127 => Output: 191 (01111111 => 10111111)
Input: 1 => Output: 2 (01 => 10)
Input: 323423 => Output: 323439 (1001110111101011111 => 1001110111101101111)
First some static tests, later on many random tests too;-)!
Hope you have fun! :-)
Quelle: codewars.com
Lösung
Pseudo-Code
Wie immer gibt's reichlich Varianten, hier ist eine meiner.
Erst die Lösungsschritte in Pseudo-Code. Los geht’s:
Lösungsschritte
Schritt 1
Wir brauchen einen Loop!
Schritt 2
Wir loopen von der gegebenen Zahl so lange, bis wir die nächste Zahl mit gleich vielen Einsen finden.
Schritt 3
Dazu macht es Sinn das Umwandeln in eine Binär-Zahl und das Zählen der Einsen in eine Hilfsfunktion auszulagern.
Code
Geil. Übersetzen wir unseren Pseudo-Code in TypeScript:
Am besten wir fangen mit der Hilfsfunktion an.
Lösungsschritte
Hier die erste Zeile meiner Hilfsfunktion:
function numOnesInBinaryOfNum(num: number): number {
Dann müssen wir die Einsen in der Binär-Version der Input-Zahl zählen:
return num.toString(2).replace(/0/g, "").length;
}
.toString(2)
wandelt
die Zahl in ihre Binär-Version um und mit
.replace()
und einer
RegEx finden und entfernen
wir alle Nullen. Dann messen wir nur noch die Länge von dem String der übrig
bleibt, also den Einsen.
Und schon können wir uns an die Hauptfunktion machen.
Die erste Zeile meiner Hauptfunktion (ich habe n
zu num
umbenannt):
export function nextHigher(num: number): number {
Dann können wir uns die Anzahl der Einsen in der Binär-Version der Input-Zahl in einer Variablen abspeichern:
const numOnesInBinaryOfInputNum = numOnesInBinaryOfNum(num);
Gleiches mit der nächsten zu prüfenden Zahl (optional):
const next = num + 1;
Dieser Schritt ist optional und dient nur der besseren Lesbarkeit.
Dann der Loop:
for (let i = next; ; i++) {
Ich nehme hier einen (unendlichen) for...of
-Loop. Die Bedingung lassen wir weg. Du kannst auch gerne while
verwenden. Wir beginnen den Loop bei der nächsten Zahl.
Dann prüfen wir, ob die aktuelle Zahl genauso viele Einsen hat wie die Input-Zahl:
if (numOnesInBinaryOfNum(i) === numOnesInBinaryOfInputNum) return i;
}
}
Wenn ja, geben wir die aktuelle Zahl zurück und beenden damit gleichzeitig den (unendlichen) For
-Loop.
Voilá! 💪
Komplettlösung
export function nextHigher(num: number): number {
const numOnesInBinaryOfInputNum = numOnesInBinaryOfNum(num);
const next = num + 1;
for (let i = next; ; i++) {
if (numOnesInBinaryOfNum(i) === numOnesInBinaryOfInputNum) return i;
}
}
function numOnesInBinaryOfNum(num: number): number {
return num.toString(2).replace(/0/g, "").length;
}