BinaryGap

Zadanie BinaryGap z jedyny problem do rozwiązania z pierwszej lekcji Codility. W razie problemów z aspektem teoretycznym serwis udostępnia odpowiedni dokument PDF.

Problem

Zadanie wymaga napisania funkcji, która dla dodatniej liczby N zwróci długość jej najdłuższej przerwy binarnej, czyli ciągu zer pomiędzy jedynkami. Funkcja powinna zwracać 0, jeśli N nie posiada binarnej przerwy.

Przykładowo, dla liczby N = 9, zapisanej binarnie 1001 przerwa wynosi 2. Liczba 20 zapisana binarnie to 10100, a jej przerwa 1.

Zakładamy także, że N jest liczbą całkowitą z zakresu [1..2147483647].

Rozwiązanie

Rozwiązanie problemy podzielimy na kilka kroków:

  1. Konwersja liczby całkowitej do postaci binarnej
  2. Pozbycie się skrajnych zer z postaci binarnej
  3. Rozdzielenie postaci binarnej znakiem ‚1’
  4. Porównanie znalezionych ciągów zer i znalezienie najdłuższego
  5. Zwrócenie długości przerwy binarnej

JavaScript

Zaczynamy od zdefiniowania zmiennych, które będą nam potrzebne w czasie działania funkcji.

Zmienna gap będzie przechowywała wartość przerwy. Początkowa wartość została ustalona na 0, co w sytuacji braku binarnej przerwy pozwoli na obsłużenie tej sytuacji. Zmienna bin będzie reprezentowała liczbę N w postaci dwójkowej. Zmienne start i stop zostaną wykorzystane do przechowania informacji o indeksie pierwszej i ostatniej jedynki w binarnej postaci liczby, a zmienna parts do przechowania wszystkich ciągów zer w postaci binarnej.


var gap = 0,
    bin = (N).toString(2),
    start = bin.indexOf('1'),
    stop = bin.lastIndexOf('1'),
    parts = bin.substring(start, stop+1).split('1');

Funkcja toString() dla liczb w JavaScript zwraca wartość liczby w postaci ciągu znaków. Opcjonalny argument funkcji umożliwia ustalenie podstawy wyliczeń, mówiąc prościej (N).toString(2) zwróci liczbę N w postaci binarnej, czego właśnie potrzebujemy.

Kolejny krok wymaga pozbycia się skrajnych zer, gdyż nawet najdłuższe ciągi zer na początku i końcu nie będą rozdzielone znakiem ‚1’ z obu stron, co jest wymagane w opisie problemu. JavaScript udostępnia konkretne funkcje indexOf() oraz lastIndexOf() do znalezienia określonego ciągu znaków w zmiennej. Zatem start zawiera miejsce wystąpienia pierwszej, a stop – ostatniej jedynki w zmiennej bin, co w określonych przypadkach może być tym samym miejscem.

To akurat nie problem, większy stanowi kwestia, kiedy ciąg „1” nie zostanie znaleziony, bo wówczas funkcje zwracają -1 jako szukanego znaku ciągu. Jednak w naszym przypadku liczba N jest zawsze dodatnia, zatem ten problem pomijamy. Wówczas należałoby w tych sytuacjach ustawić warunkowo wartości 0 zmiennym start i stop.

Następny krok to podzielenie znakiem „1” podciągu postaci binarnej, uzyskanej przez funkcję substring(start, stop), czego wynikiem będą wszystkie ciągi zer spełniające warunek przerwy binarnej i przypisanie ich do zmiennej parts. Warto zwrócić uwagę na konsekwentne ustalenie podciągu do podziału (ze skrajnymi jedynkami lub bez), choć nawet bez zwiększania wartości stop bądź zmniejszania start algorytm zachowa się tak samo, gdyż co najwyżej uwzględni dodatkowe przerwy zerowej długości.

Kolejna czynność to znalezienie najdłuższej przerwy binarnej spośród dostępnych. Najłatwiejszy sposób to iteracja w pętli for zmiennej parts, która jest tablicą i porównanie każdego elementu z dotychczasową wartości zmiennej gap pod względem długości.


for (var i = 0; i < parts.length; i++) {
  if (parts[i].length > gap) {
    gap = parts[i].length;
  }
}

Na koniec pozostaje tylko zwrócenie wartości gap, czyli przerwy binarnej.

W razie potrzeby cały przykład dostępny jest na CodePen

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *