My attempt at solving the problems in Column 1 (that have solutions unlisted in the book)
2. Since FORTRAN, etc. are not that widely used today, I'll answer this question with respect to C. C++ has a bitset implementation, but if it didn't, we could just use the bool type to create an array of bools (that function as bits).
For C, my initial thoughts are that we start off with the smallest data type we have (char, I think) and create an array. A char is 2 bytes or 16 bits, so to get the relevant bit will involve shifting and ANDing. For example, the 43rd bit will be given by the element at index (floor[43/16]) 2 - assuming a 0-based indexing system - at the (43%16) 11th position. Storing bits in order from right to left in a byte, the following pseudo code should give us the solution.
char A[1000]; // stores 8*1000 = 8000 bits
int is_set(int num) {
char element_row = A[num/16];
return (element_row >> (num%16)) & 1;
}
Similar code to set a bit. I don't think using an int should make a huge difference in terms of performance, though I haven't tried it out.
A similar question on stack overflow: Link to stack overflow - implementing a bitset in C
4. If an integer i shows up more than once, modify the pseudo code to check if i is already present. When i < 1 or i > N, we will need explicit checks before indexing into the bitset. This can be done as shown:
for every integer I in the input file:
if i < 1 or i > N: throw OutofRangeError
if A[i] == 1: throw RepeatedElementError
else A[i] = 1
Test cases (for N = 27, 000)
Input: 1 27000 (edge cases)
Input: 0 27001 (out of range)
Input: 1 1 (repeated element)
8. The given answer does not seem to be 100% accurate to me. While the probability is low, it is non-zero, or am I missing something?
