Учитывая числа от 1 до 2 ^ 32-1, один отсутствует. Как найти пропущенный номер оптимально?

Question

Вам дается 2 ^ 32-2 уникальных номера в диапазоне от 1 до 2 ^ 32-1. Невозможно поместить все числа в память (таким образом, сортировка не возможна). Вас просят найти пропущенный номер. Как лучше всего подойти к этой проблеме?

---

Предположим, вы не можете использовать большие целые числа и ограничены 32-битными целыми числами.

int с передаются через стандартный дюйм.

Answer 1

Major Edit: Поверьте мне, чтобы сделать вещи намного сложнее, чем они должны быть.

XOR всех их.

Я предполагаю, что числа от 1 до 2 ³² - 1 включительно . Это должно использовать 1 дополнительное место в памяти 32 бита.

РЕДАКТИРОВАТЬ: Я думал, что мог бы сойти с рук с помощью магии. Ах, хорошо.

Пояснение:

Для тех, кто знает, как работают коды Хэмминга, это та же идея.

Обычно для всех чисел от 0 до 2 ⁿ - 1 в каждой битовой позиции числа находится ровно 2 ^{(n - 1)} 1 с. Следовательно, при сохранении всех этих чисел на самом деле должно быть 0. Однако, так как одно число отсутствует, этот конкретный столбец даст одно, потому что в этой битовой позиции есть нечетное число единиц.

Примечание: Хотя я лично предпочитаю оператор ** для возведения в степень, я изменил свой на ^, потому что это то, что использовал OP. Не путайте ^ за xor.

Answer 2

Добавьте все числа, которые вам дали, используя вашу любимую библиотеку больших целых чисел, и вычтите эту сумму из суммы всех чисел от 1 до 2 ^ 32-1, полученной из суммы формулы арифметической прогрессии

Answer 3

Используйте побитовый оператор 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

То же самое в C #:

int[] numbers = {3, 2, 4, 5, 7, 1};

int missing = numbers.Aggregate((result, next) => result ^ next);

Console.WriteLine(missing);

Answer 4

Предполагая, что вы можете получить Size (), вы можете использовать некоторый двоичный подход. Выберите набор чисел n, где n <2 ^ 32 -2 / 2., затем получите счет. Недостающая сторона должна сообщить меньший счет. Выполните процесс итеративно, тогда вы получите ответ </p>

Answer 5

Если у вас нет XOR, то, конечно, вы можете сделать то же самое с обычной «непроверенной» суммой, то есть суммой 32-битных целых чисел с «циклическим переносом» (без «проверки переполнения», иногда известной как unchecked контекст).

Это сложение по модулю 2 ³² . Я рассмотрю «неподписанный» случай. Если ваш 32-битный int использует дополнение до двух, это то же самое. (Для математика два дополнения до сих пор просто сложение (и умножение) по модулю 2 ³² , мы выбираем только другого канонического представителя для каждого класса эквивалентности по модулю 2 ³² .)

Если бы у нас было все ненулевые 32-битные целые числа, мы бы получили:

1 + 2 + 3 + … + 4294967295 ≡ 2147483648

Один из способов реализации этого состоит в том, чтобы взять первый и последний члены вместе, они дают ноль (по модулю 2 ³² ). Тогда второй член (2) и второй последний член (4294967294) также дают ноль. Таким образом, все условия отменяются, кроме среднего (2147483648), которое затем равно сумме.

Представьте, что из этого равенства вы вычитаете одно из чисел (назовите его x) с обеих сторон символа ≡. Отсюда вы видите, что вы нашли пропущенное число, начиная с 2147483648 и вычитая (все еще unchecked) из этого числа все, что вам дали. Тогда вы получите пропущенный номер:

missingNumber ≡ 2147483648 - x1 - x2 - x3 - … - x4294967294

Конечно, это то же самое, что и решение луны, только что выполненное в кольце целых чисел по модулю 2 ³² .

---

Элегантное решение XOR (ответ Sykora) также может быть написано таким же образом, и с этим XOR функционирует как + и - одновременно. То есть, если бы у нас было все ненулевые 32-битные целые числа, то

1 XOR 2 XOR 3 XOR … XOR 4294967295 ≡ 0

и затем XOR с пропущенным номером x с обеих сторон символа ≡, чтобы увидеть, что:

missingNumber ≡ x1 XOR x2 XOR x3 XOR … XOR x4294967294