CC150 5.7

5_7.cpp

/* CC150 5.7
 * An array A contains all the integers from 0 through n, except for one number which is missing.
 * In this problem, we cannot access an entire integer in A with a single operation.
 * The elements of A are represented in binary, and the only operation we can use to access them is
 * "fetch the jth bit of A[i]," which takes constant time. Write code to find the missing integer.
 * Can you do it in 0(n) time?
 */

#include <iostream>
#include <vector>

using namespace std;

// bit access operation
int getBit(vector<int> arr, int i, int bit)
{
	return arr[i] & (1 << bit);
}

// Recursion approach
int findMissingHelper(vector<int> arr, int k)
{
	if (arr.empty())
		return 0;
	vector<int> zeros, ones;
	for (int i = 0; i != arr.size(); ++i) { // count ones and zeros in LSBs
		if (getBit(arr, i, k))
			ones.push_back(arr[i]);
		else
			zeros.push_back(arr[i]);
	}
	if (zeros.size() > ones.size()) // LSB of the missing number is 1
		return (findMissingHelper(ones, k + 1) << 1) | 1;
	else //  LSB of the missing number is 0
		return (findMissingHelper(zeros, k + 1) << 1) | 0;
}

int findMissing(vector<int> arr)
{
	if (arr.empty())
		return -1; // empty array
	return findMissingHelper(arr, 0);
}

// Iteration approach
int findMissingIter(vector<int> arr)
{
	if (arr.empty())
		return -1;
	int misNum = 0; // generate the missing number bit by bit from LSB
	vector<int> remNum = arr;
	int n = remNum.size();
	int bit = 0;
	while (n) {
		vector<int> ones, zeros;
		for (int i = 0; i != n; ++i) {
			if (getBit(remNum, i, bit))
				ones.push_back(remNum[i]);
			else
				zeros.push_back(remNum[i]);
		}
		if (zeros.size() > ones.size()) { // c0 > c1, current bit of the missing number is 1
			misNum |= (1 << bit);
			remNum = ones;
		}
		else // c0 <= c1, current bit of the missing number is 0
			remNum = zeros;
		n = remNum.size(); // uodate number of remaining numbers
		++bit; // shift left one bit per iteration
	}
	return misNum;
}

int main()
{
	vector<int> arr;
	int data;
	while (cin >> data)
		arr.push_back(data);
	cout << "Missing number is " << findMissing(arr) << endl;
	cout << "Missing number is " << findMissingIter(arr) << endl;
	return 0;
}