Codewars Lösung | Basics 08: Find next higher number with same Bits (1's)


coden
Codewars. Achieve mastery through challenge.
Daniel Kaser|5. April 2024
3 min.

Inhalt

  1. Die Fakten
  2. Beschreibung
  3. Lösung
    1. Pseudo-Code
    2. Code
  4. Feedback

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  =&gt; Output: 130 (10000001 =&gt; 10000010)
Input: 127 =&gt; Output: 191 (01111111 =&gt; 10111111)
Input: 1 =&gt; Output: 2 (01 =&gt; 10)
Input: 323423 =&gt; Output: 323439 (1001110111101011111 =&gt; 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á! 💪

Fragen?

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;
}

Feedback

Schreib mir!