• 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++

0 głosów
254 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,460 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,460 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,150 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,460 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,150 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,150 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ź 142 wizyt
pytanie zadane 8 października 2021 w C i C++ przez Ser-Ver Użytkownik (700 p.)
0 głosów
1 odpowiedź 208 wizyt
pytanie zadane 20 czerwca 2018 w C i C++ przez Hiskiel Pasjonat (22,850 p.)
+1 głos
3 odpowiedzi 5,775 wizyt
pytanie zadane 12 maja 2015 w C i C++ przez Kabiszon Użytkownik (890 p.)

88,664 zapytań

137,273 odpowiedzi

306,607 komentarzy

58,866 pasjonatów

Motyw:

Akcja Pajacyk

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

Sklep oferujący ćwiczenia JavaScript, PHP, rozmowy rekrutacyjne dla programistów i inne materiały

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...