[NotABigFan]

Mam fajne zadanko, które ponoć występuje jako pytanie rekrutacyjne do Google.

Masz tablicę nieujemnych liczb całkowitych gdzie każda liczba występuje dokładnie 3 razy oprócz jednej która występuje dokładnie raz. Wskaż liczbę która występuje dokładnie raz. Czas O(n) i uwaga pamięć O(1).

np. dla [3, 1, 4, 1, 1, 3, 3] -> 4

#programowanie #dailycodingproblem

[WhiskyRomeo]

W sziszarpie ino cyk:

uint[] array = {3, 1, 4, 1, 1, 3, 3};

Dictionary dict = new Dictionary();
foreach (uint number in array)
{
if (dict.ContainsKey(number))
{
dict[number]++;
}
else
{
dict.Add(number, 1);
}
}

uint result = dict.Where(i => i.Value == 1).Select(i => i.Key).SingleOrDefault();

Console.WriteLine(result);

Z tym stałym czasem dostępu do pamięci, w zadankach tego typu, od razu powinna się świecić lampka - "użyj hasz tejbli"! W C# to dictionary

[kawazaki]

@WhiskyRomeo: ale pamięć Twojego dicta w pesymistycznej wersji jest proporcjonalna do rozmiaru tablicy i równa O((n-1)/3) czyli O(n) - liniowa.

[b.....7]

@WhiskyRomeo: O(1) to nie stały dostęp do pamięci, ale stała pamięć pomocnicza

[WhiskyRomeo]

O(1) to nie stały dostęp do pamięci, ale stała pamięć pomocnicza

@boo007, @kawazaki: Racja. W takim razie ośmieszony - idę spać.

[S.....s]

@NotABigFan: pokombinowałbym coś, że np. sumujemy wszystkie i widzimy jaki jest mod3 (bo reszta sie zeruje) więc pewnie część można odrzucić

[NotABigFan]

@SuppressWarnings: ciepło ciepło ale nie mów tylko pisz kod

[b.....7]

@NotABigFan: Jeśli liczby to zwykłe int-y (np. 64 bitowe), to wystarczy przeiterować się 64 razy i zliczać ilość 1 na danej pozycji. Jeśli ilość 1 na danej pozycji jest podzielna przez 3, to znaczy, że szukana liczba na danej pozycji ma 0.

[NotABigFan]

@boo007: jeżeli to dobrze zrozumiałem to ma prawo działać chociaż są ciut elegantsze rozwiązania

[K.....p]

[Saly]

@KickFlip 3 + 3 + 3 + 6? @NotABigFan a to nie było zadanie z 2 powtorzeniami? Wtedy można łatwo xorem

[K.....p]

@NotABigFan
Fakt

[NotABigFan]

@Saly: Było takie ale to nie jest aż tak łatwe chociaż myślenie podobne.

[D.....o]

@NotABigFan: "xor" ale na systemie trójkowym, nie binarnym

3 0010 0010 
1 0001 0011 
4 0011 0022 
1 0001 0020 
1 0001 0021 
3 0010 0001 
3 0010 0011 4

[NotABigFan]

@Duze_piwo: Tak jess ( ͡° ͜ʖ ͡°)

[asunez]

@Duze_piwo: explain please, bo albo jest za późno i mój mózg nie ogarnia, albo po prostu jestem za głupi żeby zrozumieć

[D.....o]

@asunez: potrzebujemy operacji, która "wyczyści" wartość za 3cim zastosowaniem tej samej liczby.
XAAA ma dać z powotem X. W ten sposób "dodając" kolejne liczby z tablicy wyczyszczą się wszystkie oprócz poszukiwanej.
Taką operacją jest coś w stylu xora, z tym że nie na logicznych/binarnych wartościach, ale na systemie o podstawie 3. Gdzie 1+1=2 2+1=10. Nasz "xor" działa tak 0xor1=1 1xor1=2 2xor1=0