Missing element from array (D&C) - code design/aesthetic improvement

Question

I am trying to implement in C/C++ a 'classical' Divide and Conquer algorithm which solves the following problem "Given an array of n-1 numbers (int) from 0 to n, find the missing number".

I am using the typical algorithm: start from MSB (1) find out how many bits of 1, 0 I should have (MSB bits) (2) find out how many bits of 1, 0 I actually have (MSB bits)

split the array into 2 subarrays: one with MSBs of 0, the other with MSBs of 1. By using (1) and (2) I figure out in which subarray my number should be and I recursively call the function for the next bit (MSB-1), until my subarray contains only 1 element.

I've written the code, and it works, but I have the feeling that it isn't really that aesthetic (the function has a lot of parameters), because I had some difficulties.

Let's say that we have v = {0,1,2,3,5,6,7}. exp1 = 4 (expected number of "1" MSB bits). I know how to calculate exp1, because I know that one number is missing from 0 to 7. act1 = 3 (actual ...) So, we will have something like this: 0 1 2 3 | 5 6 7. Because act1 < exp1, we recursively call the function for the 5 6 7 part and for MSB-1.

exp1 = ? I will be unable to calculate this, because I will have no information upon the missing number. That is why I use the flagR and flagL flags. So that I know which part of the array I recursively called in order to compute exp1. But I really don't like the fact that I have been forced to use this 'trick'.

I have noticed myself that I should've forced an order in the partitioning process: the numbers that have 0 as MSB (current MSB) should be in the first part, the others in the second. I will rewrite the code.

The main() function isn't really that important for now, it serves for testing, currently.

Here is my spaghetti code:

#include <cstdio>
#include <cmath>

// get bit #j from int i
unsigned int get_bit(int i, int j)
{
  return i & (1<<j);
}

int find(int v[], int left, int right, int max_bit, int flagL, int flagR)
{
  if (left == right)
    if (flagR != 0)
      return v[left] + 1;
    if (flagL != 0)
      return v[left] - 1;
  else
  {
    int exp0 = 0; // expected bits of 0
    int act0 = 0; // actual bits of 0
    int act1 = 0; // actual bits of 1
    int exp1 = 0; // expected bits of 1

    for (int i=left+flagL;i<=right+flagR;i++)
      if (get_bit(i,max_bit) == 0)
        exp0++;
      else
        exp1++;

    for (int i=left;i<=right;i++)
      if (get_bit(v[i],max_bit) == 0)
        act0++;
      else
        act1++;

    // val_cur is the max_bit of the pivot (v[right])
    unsigned int val_cur = get_bit(v[right],max_bit);
    int i = 0;
    int k = 0;
    int man = 0;

    // divides the array into 2 subarrays
    // one subarray contains elements with max_bit = 0
    // the other contains elements with max_bit = 1
    for (k=1;k<right;k++)
    {
      if (get_bit(v[k],max_bit) == val_cur)
      {
        i++;
        man = v[i];
        v[i] = v[k];
        v[k] = man;
      }
    }
    i++;
    man = v[i];
    v[i] = v[k];
    v[k] = man;
    // i is the "border" between the subarrays

    // recursively call the function for the next bit (max_bit-1)
    // and with the correct partition
    if (get_bit(v[i],max_bit) == 1)
      if (act1 < exp1)
        return find(v,left,i,max_bit-1,0,1);
      else
        return find(v,i+1,right,max_bit-1,-1,0);
    else
      if (act0 < exp0)
        return find(v,left,i,max_bit-1,0,1);
      else
        return find(v,i+1,right,max_bit-1,-1,0);
  }
}

int main()
{
  int n = 7;
  int v[] = {7,0,4,1,3,6,2};

  // find the maximum number of bits
  int bits = 0; 
  bits = floor(log(n*1.0)/log(2*1.0));

  // call the function
  printf("%d",find(v,0,6,bits,0,1));
  return 0;
}

Answer 1

I don't follow the definition:

"Given an array of n-1 numbers (int) from 0 to n, find the missing number".

So if n == 7, as in your example code, there should be 6 numbers (n-1) in the array. There are 8 numbers in the the range "0 to n" (0,1,2,3,4,5,6,7). Perhaps the problem definition meant "0 to n-1" or "0 up to n, not including n".

Your example code has seven numbers and n == 7:

int n = 7;
int v[] = {7,0,4,1,3,6,2};

I would expect n to be 8 for an array of 7 numbers where one of the 8 is missing.

Anyway, your example works, printing '5', but if you replace, say the 2 with a 5 it now prints '3'. Unless I messed up!

---

On the code, C ignores white space (unlike say Python). Look at the if-else chain at the beginning of find:

if (left == right) 
  if (flagR != 0)
    return v[left] + 1;
  if (flagL != 0)
    return v[left] - 1;
else
{
  int exp0 = 0; // expected bits of 0

According to the indentation of statements, you intended the if (flagR != 0) and if (flagL != 0) to be dependent upon left == right, as in:

if (left == right) {
    if (flagR != 0) {
        return v[left] + 1;
    }
    if (flagL != 0) {
        return v[left] - 1;
    }
}
else {
    int exp0 = 0; // expected bits of 0

But what the compiler will see is

if (left == right) {
    if (flagR != 0) {
        return v[left] + 1;
    }
}
if (flagL != 0) {
    return v[left] - 1;
}
else {
    int exp0 = 0; // expected bits of 0

If you get the editor to re-indent the code for you (or use UNIX indent command), you will see that your indenting is wrong. The lesson is always to use braces to say explicitly what you mean.

The same goes for your other expressions:

for (int i=left+flagL;i<=right+flagR;i++)
  if (get_bit(i,max_bit) == 0)
    exp0++;
  else
    exp1++;

should be more like this:

for (int i = left + flagL; i <= right + flagR; i++) {
    if (get_bit(i, max_bit) == 0) {
        exp0++;
    } else {
        exp1++;
    }
}

In this case, there is no misunderstanding by the compiler but you should add the braces nevertheless - consider what happens if you don't add explicit braces with:

for (int i=left+flagL;i<=right+flagR;i++)
  if (get_bit(i,max_bit) == 0)
    exp0++;
  else
    exp1++;
    something_else();