Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → C++ → Знаходження дублікату в масиві за допомогою xor
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
Намагаюся знайти дублікат у масиві за допомогою xor ось так:
vector<int> nums {1, 2, 2 4};
int item { 0 };
int n = nums.size();
for (int i = 0; i < n; ++i) {
item ^= nums[i];
}
for (int i = 1; i <= n; ++i) {
item ^= i;
}
cout << item << endl;Не працює. Не можу зрозуміти чому.
Масив неправильно задано. Треба або прибрати 4, або додати 3.
А чому ви, власне, вирішили, що так можна знайти дублікат?
А чому ви, власне, вирішили, що так можна знайти дублікат?
Це використання властивості А^А = 0. Але масив має містити цілі числа від 1 до n,
які послідовно збільшуються, окрім дублікатів.
Тобто для {1, 2, 2} або {1, 2, 2, 3} — це спрацює. А от для {1, 2, 2, 4} — ні.
І в другом циклі там i<n має бути.
Цікаво, а можна XOR(1..n) знайти швидше за O(n)? Ніби у мене за логарифмічний час виходить.
Цікаво, а можна XOR(1..n) знайти швидше за O(n)? Ніби у мене за логарифмічний час виходить.
Думаю, ні. Там же треба перебирати всі елементи, неможливо відкинути якусь частину, як при бінарному пошуку.
Для масиву - не можна. А от для чисел від 1 до n - можна.
Підказка: чому дорівнює XOR усіх чисел від 1 до 2n?
Для масиву - не можна. А от для чисел від 1 до n - можна.
Підказка: чому дорівнює XOR усіх чисел від 1 до 2n?
Гадки не маю, чому він дорівнює, log2(n)? Мені був потрібен лише певний проміжок, а не всі числа від 1 до n.
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися