Cari bilangan tiga kali ganda unik dengan XOR sifar menggunakan C++

Dalam artikel ini, kita akan bercakap tentang mengira bilangan tiga kali ganda unik (x,y,z) dalam tatasusunan nombor unik yang diberikan dengan XORnya ialah 0. Jadi triple harus unik di mana ketiga-tiga elemen adalah unik dan gabungan semua triple akan dikira seperti −

Input : arr[ ] = { 5, 6, 7, 1, 3 }
Output : 2
Explanation : triplets are { 5, 6, 3 } and { 6, 7, 1 } whose XOR is zero.

Input : arr[ ] = { 3, 6, 8, 1, 5, 4 , 12}
Output : 3
Explanation : Triplets are { 3, 6, 5 }, { 1, 5, 4 } and { 4, 8, 12 } whose XOR is zero.

Cara untuk mencari penyelesaian

Kita tahu operasi XOR untuk nilai yang sama Hasilnya sentiasa sifar. Jadi pendekatan optimistik untuk mencari tiga kali ganda unik ialah mencari hasil XOR bagi dua nilai dalam tatasusunan, simpan hasilnya, dan kemudian cari tatasusunan untuk nilai yang sama dengan hasil itu. Tambahan pula, nilai hasil tidak boleh sama dengan mana-mana pasangan nilai. Sila lihat

Contoh

#include <bits/stdc++.h>
using namespace std;

int main () {
   int arr[] = { 3, 6, 8, 1, 5, 4, 12 };
   int n = sizeof (arr) / sizeof (arr[0]);
   int result;
   // count variable to keep count of pairs.
   int count = 0;
   // creating a set to store unique numbers .
   unordered_set < int >values;
   // inserting values in set.
   for (int i = 0; i < n; i++)
      values.insert (arr[i]);


   // traverse for all pairs to calculate XOR.
   for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) { // finding xor of i, j pair.
         int XR = arr[i] ^ arr[j];

         // checking if XOR value of pair present in array
         // and value should not be in pairs.
         if (values.find (XR) != values.end () && XR != arr[i] &&
            XR != arr[j])
            count++;
      }

   }
   // storing result
   result = count / 3;
   cout << "Number of unique triplets : " << result;
   return 0;
}

Output

Number of unique triplets : 3

Penjelasan kod di atas

• Buat nilai unordered_set untuk menyimpan nombor unik dalam tatasusunan yang diberikan.
• Gunakan gelung for() untuk memasukkan nilai ke dalam koleksi melalui values.insert(arr[i]).
• Gunakan dua gelung bersarang untuk mengulangi semua pasangan nombor dan mengira nilai XORnya.
• Kemudian, cari tatasusunan untuk nilai XOR dan tambahkan kiraan apabila nilai itu berada dalam tatasusunan tetapi bukan dalam pasangan.
• Simpan hasilnya sebagai kiraan / 3, supaya bilangan tiga kali ganda tiga kombinasi boleh dikira, dan apa yang kita perlukan adalah tiga kali ganda sahaja.

Kesimpulan

Artikel ini membincangkan cara mencari bilangan tiga kali ganda dengan nilai XOR 0 kami membincangkan pendekatan optimistik untuk mencari tiga kali ganda yang unik. Kami juga membincangkan program untuk menyelesaikan masalah ini dalam C++. Walau bagaimanapun, kita boleh menulis program ini dalam bahasa pengaturcaraan lain seperti Java, C, Python, dll. Semoga artikel ini bermanfaat kepada anda.

Atas ialah kandungan terperinci Cari bilangan tiga kali ganda unik dengan XOR sifar menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!