1. Mamy niemalejący ciąg nieujemnych liczb rzeczywistych (w tablicy A, indeksowanej od 0).
2. Mamy dwa indeksy, p i q, takie że 0 <= p < q < A.length.
3. Policz, ile jest takich par p i q, że A[p] * A[q] <= A[p] + A[q].
4. Złożoność czasowa rozwiązania powinna wynieść maksymalnie O(N), a pamięciowa O(1), gdzie N oznacza liczbę elementów ciągu (rozmiar tablicy).

W rzeczywistości należy wziąć pod uwagę jeszcze to, że liczby rzeczywiste są zaokrąglane, np. 10000000000.0 == 10000000001.0. Ten problem jednak tu pominę.

Zanim jednak przeczytasz, jak rozwiązać ten problem, zachęcam Cię, żeby samodzielnie się z nim zmierzyć. Jeśli tylko masz chwilę czasu, wyjmij notatnik, otwórz swoje ulubione IDE i spróbuj rozwiązać ten problem. Użyteczny może być też arkusz kalkulacyjny, aby policzyć, kiedy faktycznie dany przypadek zachodzi.

Jeśli chodzi o sam kod, możesz skorzystać z poniższego szablonu:

package io.github.dzikowski.codility;

public class Main {

    private static int count(double[] A) {
        // Your code here

    }

    public static void main(String... args) {
        double[] test = new double[] { 0.5, 1.5, 2.0, 2.0, 3.0, 9.3 };
        System.out.println(count(test));
    }
}

W powyższym przypadku program powinien wyświetlić 8.

Rozwiązanie

Poważnym ograniczeniem dla rozwiązania jest złożoność. O(N) dla złożoności czasowej oznacza, że w praktyce nie możemy zagnieżdżać pętli. Możemy skorzystać najwyżej z kilku pętli niezagnieżdżonych, w których liczba iteracji zależy liniowo od N. Złożoność pamięci O(1) oznacza, że nie powinniśmy tworzyć żadnych struktur danych, których rozmiar zależy od N.

Innymi słowy, nawet nie myśl o brute force i zliczaniu elementów w wygenerowanej dwuwymiarowej tablicy.

Przykład będzie w Javie, więc musimy też unikać rekurencji. (Na przykład w Scali naturalniej przyszło by mi użycie rekurencji, jednak z pewnych względów musimy sobie radzić z pętlami).

Na początek proponuję przyjrzeć się warunkowi, który dwie liczby muszą spełniać. Zgodnie z zadaniem, musimy policzyć takie pary indeksów p i q, że A[p] * A[q] <= A[p] + A[q]. Innymi słowy, musimy wyznaczyć takie pary liczb P i Q, że P * Q <= P + Q. W takiej sytuacji warto skorzystać z WolframAlpha, albo od razu rozpisać sobie wyniki w tabelce dla przykładowych danych.

Poniżej zamieściłem taką taką tabelkę, gdzie T oznacza, że warunek A[p] * A[q] <= A[p] + A[q] jest spełniony, a N, że nie jest spełniony.

Warunek będzie spełniony dla wartości maksymalnie na dole po prawej, dla odpowiednio dużych wartości A[p] i A[q]. Ponieważ tablica posortowana jest niemalejąco, warunek jest spełniony dla odpowiednio dużych indeksów p i q. Jeśli nie będzie spełniony dla p = A.length - 2 i q = A.length - 1 (pamiętamy o tym, że p < q), to nie będzie spełniony wcale.

Podejście, jakie wykorzystałem do rozwiązania tego problemu, było następujące:

1. Ustawiam początkowe wartości count = 0, p = 0, q = A.length - 1.

2. Jeśli p < q, sprawdzam, czy zachodzi warunek A[p] * A[q] >= A[p] + A[q].

   a) Jeśli ten warunek zachodzi, dodaję do count liczbę wartości, które spełniają warunek, czyli q - p, następnie zmniejszam q o jeden i przechodzę do punktu 2.

   b) Jeśli ten warunek nie zachodzi, zwiększam p o jeden i przechodzę do punktu 2.

3. Zwracam wartość count.

Dlaczego to działa? Zobacz na przykładzie, który pokazałem już wcześniej.

Na początku ustawiam wartości count = 0, p = 0, q = 5. Czyli tabela z danymi wygląda tak:

Ponieważ p = 0 < q = 5, sprawdzam, czy 0.5 * 9.3 <= 0.5 + 9.3. Okazuje się, że nie jest to prawda, warunek nie zachodzi, więc na pewno dla p = 0 nie znajdę żadnego q, które spełniałoby ten warunek. Mogę tym samym pominąć cały wiersz dla p = 0, więc zwiększam ‘p’ o jeden.

Ponieważ 1 < 5, sprawdzam, czy 1.5 * 9.3 <= 1.5 + 9.3. Warunek zachodzi dla p = 1, co oznacza, że dla wszystkich kolejnych p, aż do A.length - 1 także będzie zachodzić. Liczba odnalezionych par to q - p = 5 - 1 = 4, dlatego zwiększam count o 4. Mogę też nie brać już pod uwagę ostatniej kolumny, dlatego zmniejszam q o jeden.

Ponieważ 1 < 4, sprawdzam, czy 1.5 * 3.0 <= 1.5 + 3.0. Tutaj warunek też zachodzi, więc do count dodaję jeszcze 4 - 1 i zmniejszam p o jeden, aby nie uwzględniać już kolumny z indeksem 4.

Ponieważ 1 < 3, sprawdzam, czy 1.5 * 2.0 <= 1.5 + 2.0. Tym razem, warumek nie zachodzi, większ zwiększam p o jeden, aby pominąć wiersz z indeksem 1.

Ponieważ 2 < 3, sprawdzam, czy 2.0 * 2.0 <= 2.0 + 2.0. Warunek jest spełniony, więc jeszcze raz zmniejszam p i aktualizuję count.

Po tym kroku p zrównało się z q, zatem należy przerwać działanie algorytmu. Ostatecznie policzone zostały wszystkie pary, spełniające warunek. Otrzymano count = 4 + 3 + 1, czyli 8 par. Wynik jest prawidłowy, tylko że przykładowe dane nie uwzględniają jeszcze jednej rzeczy.

Uwzględnianie zer

Przypomnę jeszcze raz założenia: ciąg zawiera liczby rzeczywiste nieujemne i jest posortowany niemalejąco. Innymi słowy, na początku tablicy może znaleźć się jedno lub więcej zer, więc być może trzeba dodać jeszcze pary zer, które oczywiście spełniają warunek (0 * 0 >= 0 + 0).

Poniżej tabela, gdzie na początku ciągu dodałem trzy zera.

Jak widać, zera zachowują się nieco inaczej i musimy je dodatkowo uwzględnić. Mianowicie, oprócz poprzednich par dla nie-zer, które znalazł algorytm, należy dodać wszystkie możliwe pary zer. Można to zrobić w następujący sposób:

Dla każdego indeksu i z tablicy A (począwszy od 1),

1. jeśli A[i] == 0, dodaj i do count i przejdź do kolejnego indeksu;
2. w przeciwnym wypadku przerwij wykonywanie.

Element z indeksem 0 nie jest istotny. Jeśli element z indeksem 1, będzie zerowy, to należy dodać jedną parę, ponieważ jedno zero pojawiło się wcześniej. Jeśli element z indeksem 2, będzie zerowy, to należy dodać jeszcze dwie pary, ponieważ wcześniej pojawiły się już dwa zera. Jeśli element z indeksem k, będzie zerowy, to należy dodać jeszcze k par, ponieważ wcześniej pojawiło się już k zer. Jeśli natomiast element z indeksem k nie będzie zerowy, to przerywamy zliczanie par zer, bo wiadomo, że żadne zero już już się nie pojawi.

Pełne rozwiązanie

Ostatecznie metoda count w Javie może wyglądać tak:

    private static int count(double[] A) {

        int count = 0;
        int p = 0;
        int q = A.length - 1;

        while (p < q) {

            if (A[p] * A[q] >= A[p] + A[q]) {
                count += q - p;
                q--;
            } else {
                p++;
            }
        }

        // edge case: zeroes

        for (int i = 1; i < A.length && A[i] == 0; i++)
            count += i;

        return count;
    }

Do poczytania

Zachęcam, żeby zajrzeć na podstronę Codility dla programistów, gdzie można znaleźć ten i wiele innych problemów algorytmicznych. Niecierpliwi mogą przejrzeć odpowiedzi, na przykład te, przygotowane przez pewnego studenta jednej z pekińskich uczelni.