Samouczek na rozmowie – czy liczba jest cykliczna

To jest artykuł z serii “Samouczek na rozmowie”. W ramach tej serii staram się, między innymi, rozwiązywać zadania. Zadania te często zdarzają się na rozmowach kwalifikacyjnych.

W trakcie rozwiązywania takich zadań umiejętność szacowania złożoności obliczeniowej jest niezwykle ważna. Przyda się też umiejętność pisania testów jednostkowych. Dzięki nim bardzo łatwo przetestujesz działanie algorytmu.

• Podstawy złożoności obliczeniowej,
• Test Driven Development na przykładzie,
• Testy jednostkowe z JUnit,

Podstawą jest oczywiście znajomość języka programowania, ja używał będę Javy jednak możesz użyć dowolnego języka programowania. W opisie problemu czasami będę używał “pseudo kodu”. Przykładowe rozwiązania będą w języku Java.

• Kurs programowania w języku Java.

Czym jest liczba cykliczna

Zanim przejdę do treści zadania musisz wiedzieć czym jest liczba cykliczna. Liczba cykliczna to liczba całkowita, której cykliczne permutacje cyfr są możliwe do uzyskania przez mnożenie liczby przez kolejne liczby naturalne. Przykładową liczbą cykliczną jest 142857. Wyniki mnożenia tej liczby przez pierwsze 6 liczb naturalnych dają jej permutacje cykliczne:

142857 * 1 = 142857
142857 * 2 = 285714
142857 * 3 = 428571
142857 * 4 = 571428
142857 * 5 = 714285
142857 * 6 = 857142

Permutacja cykliczna może brzmieć jak coś skomplikowanego. W praktyce powstaje ona przez wstawianie pierwszego elementu danego łańcucha na koniec. Na przykład permutacjami cyklicznymi łańcucha znaków abcd są:

• abcd
• bcda
• cdab
• dabc

Zadanie do wykonania

Napisz funkcję isCyclic, która jako argument dostaje dowolnie dużą dodatnią liczbę całkowitą w postaci łańcucha znaków. Liczba może być poprzedzona zerami, więc "0123" jest poprawnym wejściem programu. Zadaniem jest napisanie funkcji isCyclic, która sprawdzi czy dana liczba jest liczbą cykliczną.

isCyclic("142857") == true
isCyclic("012233") == false

W przykładzie pierwsza liczba jest liczbą cykliczną. Druga linijka pokazuje przykład, dla którego isCyclic powinna zwrócić wartość false.

Od czego zależy złożoność

W przypadku tego zadania danymi wejściowymi jest łańcuch znaków. W zadaniach tego typu długość takiego łańcucha używana jest do szacowania złożoności obliczeniowej i pamięciowej. Zatem n użyte poniżej odnosi się właśnie do długości wejściowego łańcucha znaków.

Najprostsze rozwiązanie problemu

Zacznę od najprostszego rozwiązania problemu. Parametrem funkcji jest łańcuch znaków reprezentujący liczbę. Żeby zobaczyć czy ta liczba jest cykliczna wygeneruję wszystkie jej permutacje cykliczne i będę sprawdzał czy mnożąc liczbę przez kolejne wartości od 1 do N wynik będzie znajdował się we wcześniej przygotowanych permutacjach. Proszę spójrz na przykładowe rozwiązanie:

public boolean isCyclicNaive(String number) {
    String[] permutations = new String[number.length()];

    for (int index = 0; index < permutations.length; index++) {
        permutations[index] = number.substring(index) + number.substring(0, index);
    }

    BigInteger value = new BigInteger(number);
    String formatString = "%0" + number.length() + "d";

    outerLoop: for (int multiplicator = 2; multiplicator <= number.length(); multiplicator++) {
        BigInteger multiplication = value.multiply(BigInteger.valueOf(multiplicator));
        String formattedResult = String.format(formatString, multiplication);
        for (String permutation : permutations) {
            if (formattedResult.equals(permutation)) {
                continue outerLoop;
            }
        }
        return false;
    }

    return true;
}

Pierwsza pętla odpowiedzialna jest za tworzenie permutacji cyklicznych. Wewnątrz drugiej pętli sprawdzam czy mnożąc liczbę przez kolejne wartości od 2 do N uzyskam jedną z wcześniej przygotowanych permutacji. Posługuję się tutaj typem BigInteger aby móc pracować na liczbach większych niż te, które mogę przechowywać w zmiennej typu long.

Złożoność obliczeniowa

Pierwsza pętla ma złożoność Ο(n^2). Dzieje się tak ponieważ metoda substring ma złożoność Ο(n). Kolejna pętla jest zagnieżdżona i ma złożoność Ο(n^3). Tym razem złożoność “psuje” operacja multiply, która ma złożoność obliczeniową Ο(n^2). Więc finalnie złożoność obliczeniowa tego algorytmu to O(n^3).

Złożoność pamięciowa

W przypadku tego algorytmu przechowuję listę permutacji w tablicy. Tablica zawiera N permutacji. Każda permutacja ma długość N. Zatem finalna złożoność pamięciowa to Ο(n^2).

Rozwiązanie bazujące na właściwościach liczb cyklicznych

Czytając o liczbach cyklicznych dowiedziałem się kilku istotnych rzeczy:

• liczby cykliczne tworzone są na podstawie liczb pierwszych,
• liczba cykliczna zawiera o jedną cyfrę mniej od wartości liczby pierwsza użytej do jej generacji,
• liczba cykliczna jest cyklicznym rozwinięciem ułamka 1/liczba pierwsza do generacji.

Mając takie informacje podszedłem do problemu od drugiej strony. Zamiast sprawdzić czy dana liczba jest cykliczna wygenerowałem liczbę, która powstałaby na podstawie dzielenia 1/liczba pierwsza do generacji. Następnie porównuję tak uzyskaną liczbę z tą przekazaną jako argument metody. Jeśli są sobie równe wówczas przekazana liczba jest liczbą cykliczną. Proszę spójrz na implementację:

public boolean isCyclicGeneration(String number) {
    int base = 10;
    int generatingPrime = number.length() + 1;

    StringBuilder representation = new StringBuilder();

    int step = 0;
    int reminder = 1;
    do {
        step++;
        int currentValueToDivide = reminder * base;
        int currentDigit = currentValueToDivide / generatingPrime;
        reminder = currentValueToDivide % generatingPrime;
        representation.append(currentDigit);
    } while (reminder != 1 && step < generatingPrime);

    return number.equals(representation.toString());
}

Na początku ustawiam niezbędne zmienne. Następnie wewnątrz pętli obliczam kolejne wartości ułamka. Tak uzyskane liczby dodaję do bufora representation, który następnie porównuję z przekazaną liczbą.

Warunek reminder != 1 wykrywa wystąpienie okresu w rozwinięciu dziesiętnym ułamka. Więcej na temat “okresu ułamka” przeczytasz w artykule opisującym liczby zmiennoprzecinkowe.

Warunek step < generatingPrime jest potrzebny, aby uniknąć nieskończonej pętli. Taki przypadek mógłby mieć miejsce jeśli metoda jako parametr otrzymałaby liczbę, która nie jest cykliczna.

Złożoność obliczeniowa

W przypadku tego rozwiązania występuje wyłącznie jedna pętla. Zatem złożoność obliczeniowa tego algorytmu to Ο(n).

Złożoność pamięciowa

Algorytm do działania potrzebuje kilku zmiennych. Jedna z nich, representation, urośnie do długości N. Zatem w tym przypadku złożoność pamięciowa tego algorytmu to O(n).

Bardziej wydajne rozwiązanie problemu

Masz jakiś pomysł? Z chęcią poznam Twoje podejście do rozwiązania tego problemu. Wrzuć swój kod na githuba i podziel się rozwiązaniem. Pamiętaj, żeby przetestować poprawność swojego rozwiązania. Możesz to zrobić przy pomocy testów jednostkowych, które przygotowałem.

Wyślij mi swoje zadanie

Zadanie omówione w tym artykule zostało przesłane przez jednego z czytelników. Jeśli chcesz abym spróbował omówić zadanie, na które Ty trafiłeś daj znać. Zastrzegam jednak, że nie jestem alfą i omegą. Potrafię sobie wyobrazić problemy, na które nie znajdę najlepszego rozwiązania. Niemniej jednak postaram się rozwiązać to zadanie w najlepszy znany mi sposób. Zadania możesz wysłać na mój adres e-mail marcin [małpka] samouczekprogramisty.pl.

Często firmy zastrzegają sobie to, żeby nie rozpowszechniać zadań, które były na rozmowie kwalifikacyjnej. Jeśli tak było w Twoim przypadku proszę uszanuj wolę danej firmy i nie przesyłaj mi takiego zadania.

Dostając zadanie od Ciebie zakładam, że mogę je opublikować na blogu.

Podsumowanie

Po przeczytaniu artykułu znasz dwa sposoby rozwiązania zadanego problemu. Znasz złożoność pamięciową i obliczeniową każdego z rozwiązań. Jesteś o jedno zadanie lepiej przygotowany do rozmowy kwalifikacyjnej ;).

Przykładowe rozwiązania, przedstawione w artykule znajdziesz na samouczkowym githubie. Kod zawiera także testy jednostkowe, których użyłem do weryfikacji poprawności działania algorytmów.

Jeśli nie chcesz pominąć kolejnych artykułów z tej serii dopisz się do samouczkowego newslettera i polub Samouczka na Facebooku. Jak zwykle, jeśli masz jakiekolwiek pytania proszę zadaj je w komentarzach. Postaram się pomóc ;). Do następnego razu!

Pobierz opracowania zadań z rozmów kwalifikacyjnych

Przygotowałem rozwiązania kilku zadań algorytmicznych z rozmów kwalifikacyjnych. Rozkładam je na czynniki pierwsze i pokazuję różne sposoby ich rozwiązania. Dołącz do grupy ponad 6147 Samouków, którzy jako pierwsi dowiadują się o nowych treściach na blogu, a prześlę je na Twój e-mail.