Разработайте алгоритм «разделяй и властвуй», который может определить отсутствующее целое число

Question

Для данного массива A, содержащего в некотором порядке все k-битные неотрицательные целые числа, кроме одного, найти недостающее целое число со следующим ограничением:

Вам разрешено делать только две вещис одним из этих целых чисел:

1. Получить значение его i-го бита
2. Поменять их местами в массиве

Например: if kЕсли 3, то массив будет содержать все, кроме одного, целые числа от 0 до 7 включительно, задача состоит в том, чтобы найти отсутствующее целое число.

Answer 1

Вы должны проверить, что каждый бит (например, если k = 3, вам нужно проверить, что все 3 бита) присутствуют 2 ^ k-1 раз как 0 и 1.

Если вы уверены в инварианте списка, который вы обрисовали в общих чертах (отсутствует только одно число и нет дубликатов) - уверен, что он всегда выполняется - тогда вы можете просто проверить только один, произвольный бит содержит условие, описанное выше .

Например, скажем, что инвариант выполняется, k = 3, и у вас есть список [0-7], исключая 6. Для каждого числа в списке получите его первый бит (наименее значимый) и выполните следующие действия:

if bit value = 0 then zeroValues++;<br> if bit value = 1 then oneValues++;

zeroValues должно равняться oneValues, и оба должны равняться 2^k-1, в данном случае 4.

Редактировать : Перечитывая свой вопрос, вы ищете все число. Чтобы найти целое целое значение, которое вы ищете, просто выполните процедуру для всех битов. Для каждого бита, который вы делаете, вы обнаружите, что отсутствует значение 0 или 1. Отсутствующее значение - это битовое значение в целочисленном результате. Делая это для всех битов, вы найдете полное битовое представление вашего целого числа.

Answer 2

Подсказка: вы можете узнать, четное или нечетное пропущенное число?

Answer 3

Для подсказки для совершенно другого подхода, вы можете отсортировать массив?