Remove a key from a hash table efficiently
C++, not C

First things first, I note that remove is a free function. But that's not how we would do something like this in C++. We would prefer to have a type HashTable in which we'd write:

class HashTable {
public:
   ...
   bool remove(int key);
   ...

private:
   int hash(int );

   std::vector&lt;int&gt; table; // vector is better than int*
                           // table is a better name than H
};


Your naming also could use some work - what is x and what is m? I'm guessing m is the capacity and x is the key that we're erasing, but where are the values? We just have int H[], so is this more like a hash set than a hash table? It's unclear.

Looping and separation of concerns

The hash function should just do the hashing (and thus shouldn't take in the capacity). The loop itself should loop over slots, not indices - this will localize your modulo operation so it doesn't creep in everywhere:

int next(int i) {
    return (i+1) % table.size();
}

bool remove(int key) {
    int i = hash(key) % table.size(); 
    if (table[i] == EMPTY) {          // break early
        return false;
    }

    for (; table[i] != EMPTY; i = next(i)) {
        if (table[i] == key) {
            table[i] = EMPTY;

            for (int k = next(i); table[k] != EMPTY; k = next(k)) {
               ...
            }

            return true;
        }
    }

    return false;
}


Once you reorient looping over additive indices to looping over actual indices, the inner body becomes more straightforward too:

int old_key = table[k];
table[k] = EMPTY;
insert(old_key);


Find the slot

Your i loop is all about finding the slot where the key is at. The body of that loop isn't really a loop, it's a find-type algorithm. So let's rewrite it like one:

bool remove(int key) {
    int i = hash(key) % table.size(); 
    for (; table[i] != key; i = next(i)) {
        if (table[i] == EMPTY) {          // break early
            return false;
        }
    }

    // now, table[i] == key
    table[i] = EMPTY;
    for (int k = next(i); table[k] != EMPTY; k = next(k)) {
        int old_key = table[k];
        table[k] = EMPTY;
        insert(old_key);
    }

    return true;
}


EMPTY

In addition to not really being a hash table, you're seemingly limiting the possible valid keys to exclude something like 0 or -1 or whatever the value of EMPTY is. May be worth separating the key from the empty concept.