Вам даны 2 ^ 32-2 уникальных номера, которые варьируются от 1 до 2 ^ 32-1. Невозможно поместить все числа в память (таким образом, сортировка не является вариантом). Вас попросят найти недостающий номер. Какой был бы лучший подход к этой проблеме?
Предположим, вы не можете использовать большие целые числа и ограничены 32-битными ints.
int передаются через стандартный.
Major Edit: Поверьте мне, чтобы сделать вещи намного сложнее, чем они должны быть.
Я предполагаю здесь, что числа от 1 до 2 32 - 1 включительно. Это должно использовать 1 дополнительное место памяти 32 бита.
РЕДАКТОР: Я думал, что могу уйти от магии. Хорошо.
Для тех, кто знает, как работают коды Хэмминга, это та же идея.
В принципе, для всех чисел от 0 до 2 n - 1 в каждой битовой позиции числа есть ровно 2 (n - 1) 1s. Поэтому xoring все эти числа должны фактически давать 0. Однако, поскольку отсутствует один номер, этот конкретный столбец даст один, потому что в этой позиции бит есть нечетное число.
Примечание. Хотя я лично предпочитаю оператор ** для возведения в степень, я изменил свое значение на ^, потому что это то, что использовал OP. Не путайте ^ для xor.
Добавьте все числа, которые вы отдали, используя вашу любимую большую целочисленную библиотеку, и вычтите эту сумму из суммы всех чисел от 1 до 2 ^ 32-1, полученных из сумма формулы арифметической прогрессии
Использовать побитовый оператор XOR. Вот пример в JavaScript:
var numbers = [6, 2, 4, 5, 7, 1]; //2^3 exclude one, starting from 1
var result = 0;
//xor all values in numbers
for (var i = 0, l = numbers.length; i < l; i++) {
result ^= numbers[i];
}
console.log(result); //3
numbers[0] = 3; //replace 6 with 3
//same as above in functional style
result = numbers.reduce(function (previousValue, currentValue, index, array) {return currentValue ^= previousValue;});
console.log(result); //6
То же самое в С#:
int[] numbers = {3, 2, 4, 5, 7, 1};
int missing = numbers.Aggregate((result, next) => result ^ next);
Console.WriteLine(missing);
Предполагая, что вы можете получить Size(), вы можете использовать некоторый двоичный подход. Выберите набор чисел n, где n < 2 ^ 32 -2/2. затем получите счет. Недостающая сторона должна сообщать о более низком счетчике. Сделайте процесс итеративно, после чего вы получите ответ
Если у вас нет XOR, то, конечно, вы можете сделать то же самое с обычной "непроверенной" суммой, то есть суммой 32-битных целых чисел с "циклическим переносом" (без "проверки переполнения", иногда называемой unchecked контекстом).
Это дополнение по модулю 2 32. Я рассмотрю "неподписанный" случай. Если у вас 32-битный int использует два дополнения, это точно так же. (Для математика два дополнения - это всего лишь сложение (и умножение) по модулю 2 32 мы выбираем только другого канонического представителя для каждого класса эквивалентности по модулю 2 32).
Если бы у нас были все ненулевые 32-битные целые числа, мы бы имели:
1 + 2 + 3 + … + 4294967295 ≡ 2147483648
Один из способов реализации этого состоит в том, чтобы взять первый и последний члены вместе, они дают ноль (по модулю 2 32). Тогда второй член (2) и второй последний член (4294967294) также дают ноль. Таким образом, все условия отменяются, кроме среднего (2147483648), которое затем равно сумме.
Из этого равенства, представьте, что вы вычесть одно из чисел (назовем его x) на обеих сторонах ≡ символа. Отсюда видно, что вы нашли пропущенное число, начиная с 2147483648 и вычитая (все еще unchecked) из этого числа все, что вам дали. Тогда вы в конечном итоге с отсутствующим номером:
missingNumber ≡ 2147483648 - x1 - x2 - x3 - … - x4294967294
Конечно, это то же самое, что решение для луны, только что выполненное в кольце целых чисел по модулю 2 32.
Элегантное решение XOR (ответ sykora) также может быть написано таким же образом, и с этим XOR функционирует как + и - одновременно. То есть, если бы у нас были все ненулевые 32-битные целые, то
1 XOR 2 XOR 3 XOR … XOR 4294967295 ≡ 0
а затем XOR с отсутствующим числом x по обе стороны от символа ≡ чтобы увидеть, что:
missingNumber ≡ x1 XOR x2 XOR x3 XOR … XOR x4294967294