Maximum subset which has no sum of two divisible by K

Question

I am given the set {1, 2, 3, ... ,N}. I have to find the maximum size of a subset of the given set so that the sum of any 2 numbers from the subset is not divisible by a given number K. N and K can be up to 2*10^9 so i need a very fast algorithm. I only came up with an algorithm of complexity O(K), which is slow.

Answer 1

first calculate all of the set elements mod k.and solve simple problem: find the maximum size of a subset of the given set so that the sum of any 2 numbers from the subset is not equal by a given number K. i divide this set to two sets (i and k-i) that you can not choose set(i) and set(k-i) Simultaneously.

int myset[]
int modclass[k]

for(int i=0; i< size of myset ;i++)
{
    modclass[(myset[i] mod k)] ++;
}

choose

for(int i=0; i< k/2 ;i++)
{ 
    if (modclass[i] > modclass[k-i])
    {
        choose all of the set elements that the element mod k equal i
    }
    else
    {
        choose all of the set elements that the element mod k equal k-i
    }
}

finally you can add one element from that the element mod k equal 0 or k/2.

this solution with an algorithm of complexity O(K).

you can improve this idea with dynamic array:

for(int i=0; i< size of myset ;i++)
{
    x= myset[i] mod k;
    set=false;
    for(int j=0; j< size of newset ;j++)
    {
        if(newset[j][1]==x or newset[j][2]==x)
        {
            if (x < k/2)
            {
                newset[j][1]++;
                set=true;
            }
            else
            {
                newset[j][2]++;
                set=true;
            }
        }
    }
    if(set==false)
    {
        if (x < k/2)
        {
            newset.add(1,0);
        }
        else
        {
            newset.add(0,1);
        }
    }
}

now you can choose with an algorithm of complexity O(myset.count).and your algorithm is more than O(myset.count) because you need O(myset.count) for read your set. complexity of this solution is O(myset.count^2),that you can choose algorithm depended your input.with compare between O(myset.count^2) and o(k). and for better solution you can sort myset based on mod k.