The question is to find a pair of integers (a,b) from a set M of unsigned integers, where a-b is a multiple of n. Given a positive integer n, which is less than the length (m) of set M. Here is the snippet I have written.

I am not too sure about the time complexity of this algorithm w.r.t the length of M and the value of n. In the exlude function, worst case is O(m). Then it is within a for loop over m, then O(m^2). In addition, X initialization scales with n, so O(n) here. In total: O(m^2) O(n), ignoring the other O(1)s. Is this correct?

Also, should I take r = x % n as O(1)?

Any coding related advices on the codes here are welcome!!! Big thx!

//array X is intialized of size n, all -1. Here the code is omitted.
    for (int i = 0; i < m; i  )
    {
        if (currentLength > 1)
        {
            index = rand() % currentLength;
            x = setM[index];
            exclude(setM, index, &currentLength);
            r = x % n;
            if (X[r] == -1)
            {
                X[r] = x;
            }
            else
            {
                printf("The pair: (%i, %i)\n", X[r], x);
                break;
            }
        }

        else
        {
            break;
        }
        currentLength -= 1;
    }

// to exclude an element based on index, then shift all elements behind by 1 slot

void exclude(int* array, int index, int* length_ptr)
{
    if (index != *length_ptr - 1)
    {
        for (int i = index; i < *length_ptr - 1; i  )
        {
            array[i] = array[i   1];
        }
    }
}

CodePudding user response：

You need to find two numbers x and y that x%n==y%n. It easy. Use a hash table with a key of x %n. Add consequtive numbers from the set until you find a duplicate. It would be the desired pair. Complexity is O(M).

CodePudding user response：

Also, should I take r = x % n as O(1)?

Yes, it's O(1)

I am not too sure about the time complexity of this algorithm ... In total: O(m^2) O(n)?

Well, kind of but there is more to it than that. The thing is that m and n is not independent.

Consider the case n = 2 and let m be increasing. Your formula would give O(m^2) but is that correct? No. Since there will only be 2 possible results from % n (i.e. 0 and 1) the loop for (int i = 0; i < m; i ) can only run 3 times before we have a match. No matter how much you increase m there can never be more than 3 loops. In each of these loops the exclude function may move near m elements in worst case. In general the for (int i = 0; i < m; i ) can never do more than n 1 loops.

So for m being larger than n you rather have O(n*m) O(n). When keeping n constant this turns into just O(m). So your algorithm is just O(m) with respect to m.

Now consider the case with a constant m and a large increasing n. In this case your formula gives O(m^2) O(n). Since m is constant O(m^2) is also constant so your algorithm is just O(n) with respect to n.

Now if you increase both m and n your formula gives O(m^2) O(n). But since m and n are both increased, O(m^2) will eventually dominate O(N), so we can ignore O(N). In other words, your algorithm is O(M^2) with respect to both.

To recap:

O(m)   for constant n and increasing m
O(n)   for constant m and increasing n
O(m^2) for increasing n and increasing m

Any coding related advices on the codes here are welcome

Well, this index = rand() % currentLength; is just a bad idea!

You should always test the last element in the array, i.e. index = currentLength - 1;

Why? Simply because that will turn exclude into O(1). In fact you won't even need it! The exclude will happen automatically when doing currentLength -= 1;

This change will improve complexicity like

O(1)      for constant n and increasing m
O(n)      for constant m and increasing n
O(m) O(n) for increasing n and increasing m

The O(m) O(n) can be said to be just O(m) (or just O(n)) as you prefer. The main thing is that it is linear.

Besides that you don't need currentLength. Change the main loop to be

for (int i = m-1; i >= 0; --i)

and use i as index. This simplifies your code to:

for (int i = m-1; i >= 0; --i)
{
    r = setM[i] % n;
    if (X[r] == -1)
    {
        X[r] = setM[i];
    }
    else
    {
        printf("The pair: (%i, %i)\n", X[r], setM[i]);
        break;
    }
}