Last active
August 29, 2015 14:04
-
-
Save ivycheung1208/dd204c15820dbc436bc0 to your computer and use it in GitHub Desktop.
CC150 5.7
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment