• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Znajdź wartość, która występuje w nieparzystej liczby elementów C++

VPS Starter Arubacloud
0 głosów
319 wizyt
pytanie zadane 9 czerwca 2016 w C i C++ przez Macek Kolo Mądrala (5,480 p.)
edycja 9 czerwca 2016 przez Macek Kolo

Kod:

#include <iostream>
#include <vector>

using namespace std;

int solution(vector<int> &A)
{
    int result = 0;
    for(int i : A)
    {
        result ^= i;
    }
    return result;
}

int main()
{
    vector<int> vec {9,3,9,3,9,6,9};
    cout << solution(vec) << endl;
    return 0;
}

Może mi ktoś powiedzieć z jakich ot własności liczb binarnych korzysta ta funkcja, że zwraca dobry wynik? Bo ja bym nie wpadł, że wystarczy xorować... Dlaczego to działa? 

Najpierw result ma 0, potem 9, nastepnie 10. Jak się to ma do tych liczb w vektorze? 

 

Strona z zadaniem https://codility.com/programmers/task/odd_occurrences_in_array/

komentarz 9 czerwca 2016 przez Patrycjerz Mędrzec (192,340 p.)
Przepraszam, ale po tytule w ogóle nie mogę się domyśleć, co ta funkcja robi.
komentarz 9 czerwca 2016 przez Macek Kolo Mądrala (5,480 p.)
no właśnie dokładnie to co jest napisane w tytule :)
komentarz 10 czerwca 2016 przez Patrycjerz Mędrzec (192,340 p.)

Jeśli wziąłeś tytuł zadania z translatora, to czego się dziwisz, że go nie zrozumiałem.

Po drugie, jest on nieadekwatny do tego, co ma robić funkcja solution, gdyż nic nie mówi o szukaniu liczby nie pasującej do wzorca.

komentarz 10 czerwca 2016 przez MetRiko Nałogowiec (37,110 p.)
Tu chyba nie chodziło o liczbę nie pasującą do wzorca, a bardziej ogólnie o element występujący nieparzystą ilość razy.. przynajmniej to wywnioskowałem wypisując sobie kolejne kroki.
1
komentarz 10 czerwca 2016 przez Patrycjerz Mędrzec (192,340 p.)

Racja, bo słowo unpaired mnie zmyliło, co nie zmienia to faktu, że tytuł jest mocno niejasny.

1 odpowiedź

+2 głosów
odpowiedź 9 czerwca 2016 przez MetRiko Nałogowiec (37,110 p.)
wybrane 10 czerwca 2016 przez Macek Kolo
 
Najlepsza
Xor jest przemienny (jak dodawanie), tak więc a^b jest równe b^a ponadto, a^a jest równe 0.
Skoro w wektorze znajduje się tylko 1 liczba bez pary to wynikiem będzie właśnie ona, ponieważ reszta się zniweluje.
Tu masz dokładnie rozpisane kroki:
r:
0(-) - 0000
1(9) - 0000 xor 1001 = 1001 = 9
2(3) - 1001 xor 0011 = 1010 = 10
3(9) - 1010 xor 1001 = 0011 = 3
4(3) - 0011 xor 0011 = 0000 = 0
5(9) - 0000 xor 1001 = 1001 = 9
6(6) - 1001 xor 0101 = 1101 = 13
7(9) - 1101 xor 1001 = 0101 = 6
Mam nadzieję, że o to ci chodziło :D
komentarz 10 czerwca 2016 przez Macek Kolo Mądrala (5,480 p.)
Dzięki, to teraz pytanie. Jak wpadać na takie rzeczy przy pisaniu kodu? Czy jedynym wyjściem jest robić tak dużo przykładów, że w końcu zaczną się powtarzać, czy jak?

To zadanie jest z codiliy, robiłem też inne i mimo, że przy większości u mnie wszystko działało to na stronie wywalało błąd np. czasu. Z programowaniem nie mam problemu, właśnie moje algorytmy ssą :(
1
komentarz 10 czerwca 2016 przez MetRiko Nałogowiec (37,110 p.)
Co do wpadania na takie rzeczy.. myślę, że tu jest potrzebna nie tylko praktyka (rozwiązywanie tego typu problemów), ale i również znajomość różnych twierdzeń matematycznych oraz umiejętność poprawnego ich wykorzystania w praktyce.. np. jeżeli chcesz znaleźć dwie ostatnie cyfry wartości n! nawet dla n=1000.. to wystarczy pomyśleć, że dla n>=10 silnia jest mnożona przez 2, 5 i 10.

Podobne pytania

+1 głos
1 odpowiedź 535 wizyt
pytanie zadane 8 października 2021 w C i C++ przez Ser-Ver Użytkownik (820 p.)
0 głosów
1 odpowiedź 384 wizyt
pytanie zadane 20 czerwca 2018 w C i C++ przez Hiskiel Pasjonat (22,830 p.)
+1 głos
3 odpowiedzi 7,258 wizyt
pytanie zadane 12 maja 2015 w C i C++ przez Kabiszon Użytkownik (890 p.)

92,454 zapytań

141,262 odpowiedzi

319,089 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...