Angka yang Muncul Ganjil Kali

Pelajaran 10 dari 17 dalam kursus Manipulasi Bit di Coddy.

Ingat tantangan yang kamu selesaikan dalam pelajaran "XOR operator", saat kita menggunakan sifat-sifat XOR. Pertanyaan yang akan kita selesaikan dalam pelajaran ini cukup mirip dengan tantangan itu. Jadi, masalah yang akan kita bahas adalah:

Temukan elemen yang muncul dalam jumlah ganjil di array yang diberikan.

Kamu akan diberi sebuah array yang berisi beberapa elemen bilangan bulat. Dari semua elemen tersebut, setiap elemen muncul dalam jumlah genap, kecuali satu elemen.

Misalkan kita memiliki array int Arr[11] = { 2, 5, 6, 6, 6, 4, 5, 2, 5, 4, 5}.

Dalam array ini,

'2' muncul sebanyak dua kali (genap).
'5' muncul sebanyak empat kali (genap).
'6' muncul sebanyak tiga kali (ganjil).
'4' muncul sebanyak dua kali (genap).

Jadi, angka '6' muncul dalam jumlah ganjil. Inilah yang perlu kita temukan dalam soal ini, yaitu angka yang muncul dalam jumlah ganjil di array.

Seperti yang kita lihat dalam pelajaran operator "XOR", untuk sebuah angka 'x',

x ⊕ x = 0 (simbol '⊕' mewakili operasi XOR)
x ⊕ 0 = x

Dengan menggunakan sifat pertama, semua elemen yang muncul dalam jumlah genap akan menghasilkan 0 saat di-XOR. Dengan menggunakan sifat kedua, kita akan mendapatkan angka yang muncul dalam jumlah ganjil.

Jadi, melakukan operasi XOR pada semua elemen array akan menghasilkan output. Selesai, itulah solusi masalahnya. Mudah, bukan?

Kompleksitas waktu untuk masalah ini adalah O(n) karena kita harus menelusuri seluruh array dan melakukan operasi XOR pada semua elemennya.

Tantangan

Mudah

Lengkapi fungsi "OddElement" agar mengembalikan elemen yang muncul dalam jumlah ganjil pada array yang diberikan. Gunakan operator XOR untuk menyelesaikan masalah ini.

Coba sendiri

#include <iostream>
#include <vector>
using namespace std;

int OddElement(vector<int> arr) {
    // Tulis kodemu di sini
}

Semua pelajaran di Manipulasi Bit

1Pengenalan dan dasar-dasar

Apa itu manipulasi bit?Mengapa kita membutuhkan manipulasi bit?Bilangan biner dan desimal Operator NOT dan OR Operator AND Operator XOR Operator geser ke kanan dan kiri Ringkasan operator bitwise

2Algoritma Bit

Pangkat 2Angka yang Muncul Ganjil KaliJumlah Bit Bernilai 1 Rotasi Bit pada Angka I Rotasi Bit pada Angka II

3Tantangan latihan

Tina dan penugasan bitnya XORty Temukan K Temukan Jumlah Minimum

Latihan sendiri: Compiler C++ online